leetcode
leetcode 901 ~ 950
将数组分成和相等的三个部分

将数组分成和相等的三个部分

难度:

标签:

题目描述

代码结果

运行时间: 27 ms, 内存: 21.9 MB


/*
 * 思路:
 * 使用 Java Stream 对数组元素进行处理。
 * 先计算总和,如果不能被 3 整除,直接返回 false。
 * 否则,求出每部分的和 totalSum / 3。然后使用流操作对数组进行遍历,
 * 通过累加元素找到每个部分的边界,使用过滤器找到符合条件的部分数量。
 */
import java.util.Arrays;

public class Solution {
    public boolean canThreePartsEqualSum(int[] arr) {
        int totalSum = Arrays.stream(arr).sum();
        if (totalSum % 3 != 0) return false;
        int partSum = totalSum / 3;
        int[] counts = new int[1]; // 使用数组存储计数器,以便在 lambda 表达式中修改
        Arrays.stream(arr).reduce(0, (currentSum, num) -> {
            currentSum += num;
            if (currentSum == partSum) {
                counts[0]++;
                return 0; // 重新开始计数
            }
            return currentSum;
        });
        return counts[0] >= 3;
    }
}

解释

方法:

首先计算数组 arr 的总和 total。如果 total 不是 3 的倍数,则直接返回 False,因为不能平均分成三个相同的部分。如果 total 是 3 的倍数,则定义 each_sum 为 total 除以 3 的结果。接下来,遍历数组 arr,累加元素值到临时变量 sumi。每当 sumi 等于 each_sum 时,将 sumi 重置为 0,并将 count(记录达到 each_sum 的次数)加 1。如果 count 达到 3 次,即在数组结束前已找到三个部分和为 each_sum,则返回 True。如果遍历完成后,没有找到三个这样的部分,则返回 False。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在算法实现中,当找到三个和为`each_sum`的部分后为什么直接返回True?是否需要验证第三部分确实延续到数组的末尾?
当算法在遍历过程中第三次达到`each_sum`时,意味着已经成功划分出三个和为`each_sum`的部分。此时,算法直接返回True是基于这样的逻辑:前两部分和第三部分的总和等于整个数组的总和,即3倍的`each_sum`。由于总和已经被验证为3的倍数,找到了三个这样的部分就意味着其余的元素和也必然是`each_sum`。因此,不需要额外验证第三部分是否延续到数组的末尾,它自然满足条件。
🦆
为什么在`sumi`达到`each_sum`后需要将`sumi`重置为0,这种方法是否保证了每个部分都是连续的子数组?
在`sumi`达到`each_sum`后将`sumi`重置为0是为了重新开始计算下一个部分的和,这确保了每个部分都是从前一个部分结束的地方连续开始的。由于累加是连续的,每次重置`sumi`都意味着开始新的连续子数组。这种方法确保了每个部分不仅和为`each_sum`,而且是数组中连续的片段。
🦆
如果数组`arr`中存在负数或零,这是否影响算法的正确性和部分的划分?
数组中存在的负数或零不会影响算法的正确性。算法的目标是找到三个和为`each_sum`的连续部分,不论这些部分中的元素是正数、负数还是零。只要这些部分的和达到了预定的`each_sum`,无论组成元素的具体值如何,都满足题目要求。因此,包含负数或零的数组同样适用于此算法。
🦆
算法中的`count`变量在达到3之后,算法就终止返回True。如果`count`在数组未完全遍历前就达到3,这是否可能导致误判?
如果`count`在数组未完全遍历前就达到3,这实际上不会导致误判。这是因为算法确保了每次`count`增加时,已找到的部分和必然是`each_sum`。一旦`count`达到3,意味着我们已经找到了三个部分的总和等于3倍的`each_sum`,即数组的总和。此时,即使数组没有遍历完,剩余部分的总和必然为0,这不会影响已经找到的三个部分满足题目条件。

相关问题