将数组分割成和相等的子数组
难度:
标签:
题目描述
代码结果
运行时间: 181 ms, 内存: 16.3 MB
/*
* 将数组分割成和相等的子数组
* 题目思路:
* 1. 使用流操作计算数组的总和,判断能否被2整除,如果不能,直接返回false。
* 2. 遍历数组,用一个变量记录当前子数组的和。
* 3. 当当前子数组的和等于总和的一半时,说明可以分割,返回true。
* 4. 如果遍历结束还没有找到这样的子数组,返回false。
*/
import java.util.Arrays;
public class Solution {
public boolean canPartition(int[] nums) {
int totalSum = Arrays.stream(nums).sum();
if (totalSum % 2 != 0) {
return false;
}
int target = totalSum / 2;
int[] partialSum = new int[1];
return Arrays.stream(nums).anyMatch(num -> {
partialSum[0] += num;
return partialSum[0] == target;
});
}
}
解释
方法:
这个题解的思路是将问题转化为寻找四个子数组和相等的问题。首先使用前缀和数组 ps 计算从数组开头到每个位置的元素和,方便快速计算任意区间和。然后枚举第一个分割点 i 和第二个分割点 j,计算前两个子数组的和 a 和 b。如果 a 和 b 相等,就在 j 右侧寻找满足区间和等于 b 的位置 k,这样四个子数组的和就都相等了。为了加速寻找过程,使用哈希表 cache 提前记录所有可能的最后一个子数组的和及其对应的右端点位置,避免再次遍历。同时使用 visited 集合记录已经检查过的 b 值,避免重复计算。
时间复杂度:
O(n^2)
空间复杂度:
O(n)
代码细节讲解
🦆
在算法中,为什么需要使用前缀和数组ps,它如何帮助优化计算子数组的和?
▷🦆
算法中提到使用哈希表cache来存储子数组和及其右端点位置,这种方法有哪些可能的缺点或限制?
▷🦆
在遍历过程中,为什么选择从索引1开始枚举第一个分割点i,而不是从0开始?
▷🦆
为什么在内层循环中,第二个分割点j的起始位置是i+2而不是i+1?
▷