和相同的二元子数组
难度:
标签:
题目描述
代码结果
运行时间: 206 ms, 内存: 16.8 MB
/*
* 题目思路:
* 使用 Java Stream 的方式解决问题。虽然 Java Stream 处理这种问题可能不如直接使用循环方便,但可以通过流的方式简化代码。
* 同样利用前缀和的概念,配合 Collectors.groupingBy 和 Collectors.counting 等方法统计满足条件的子数组数量。
*/
import java.util.HashMap;
import java.util.Map;
import java.util.stream.IntStream;
public class SolutionStream {
public int numSubarraysWithSum(int[] nums, int goal) {
Map<Integer, Long> prefixSumCount = new HashMap<>();
prefixSumCount.put(0, 1L);
int[] prefixSum = {0};
return (int) IntStream.of(nums)
.map(num -> prefixSum[0] += num)
.mapToLong(sum -> {
long count = prefixSumCount.getOrDefault(sum - goal, 0L);
prefixSumCount.put(sum, prefixSumCount.getOrDefault(sum, 0L) + 1);
return count;
})
.sum();
}
}
解释
方法:
该题解利用滑动窗口的思想处理子数组问题。对于goal为0的特殊情况,单独处理,统计连续的0的子数组个数。对于goal不为0的情况,遍历数组,每遇到1,则减少goal的值,如果goal减为0,则说明从当前窗口的开始到当前位置的子数组是一个有效的子数组。通过调整窗口的起始位置i,直到窗口内的和再次大于goal,过程中统计每次有效的子数组个数。这种方法只需要遍历数组一次,同时调整窗口起始位置,直到整个数组都被检查过。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在处理goal为0的情况时,算法是如何确保不漏计连续0的子数组的?
▷🦆
对于goal不为0的情况,当遇到1且减少goal的值后,如何处理累加的子数组计数以确保没有重复计数?
▷🦆
请问在调整窗口起始位置i时,为什么选择在`goal == 0`的条件下进行调整?这种条件下的调整有什么特别的考虑吗?
▷