将数组分成和相等的三个部分
难度:
标签:
题目描述
代码结果
运行时间: 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?是否需要验证第三部分确实延续到数组的末尾?
▷🦆
为什么在`sumi`达到`each_sum`后需要将`sumi`重置为0,这种方法是否保证了每个部分都是连续的子数组?
▷🦆
如果数组`arr`中存在负数或零,这是否影响算法的正确性和部分的划分?
▷🦆
算法中的`count`变量在达到3之后,算法就终止返回True。如果`count`在数组未完全遍历前就达到3,这是否可能导致误判?
▷