如何应用前缀和与哈希表嵌套循环深度组合实战在 $O(N)$ 时间内求解任意复杂连续子数组和的临界值-java教程-PHP中文网

前缀和加哈希表可在o(n)时间内解决连续子数组和问题，无需嵌套循环；通过presum[i]−presum[j]快速计算子数组和，并用哈希表以o(1)查找满足条件的前缀和，显著优于o(n²)或o(n³)暴力解法。

如何应用前缀和与哈希表嵌套循环深度组合实战在 $o(n)$ 时间内求解任意复杂连续子数组和的临界值

直接用前缀和加哈希表，就能在 O(N) 时间内解决连续子数组和的临界值问题，根本不需要嵌套循环——所谓“嵌套循环深度组合”其实是暴力解法的特征，而前缀和+哈希表的目标恰恰是消除嵌套。

为什么不用嵌套循环？

暴力枚举所有子数组起点和终点，再对每个子数组求和，时间复杂度是 O(N³)（双层定界 + 内层累加）或至少 O(N²)（预处理前缀和后双层定界）。这在 N > 10⁴ 时必然超时。前缀和+哈希表的核心价值，就是把“找满足条件的子数组个数/长度/存在性”转化为“单次遍历中查表匹配”，彻底避开双重索引循环。

前缀和怎么让子数组和变成一次相减？

定义 preSum[i] 为 nums[0..i−1] 的和，且 preSum[0] = 0。那么任意子数组 nums[j..i−1] 的和 = preSum[i] − preSum[j]。
例如 nums = [2, −1, 3, 1]，则 preSum = [0, 2, 1, 4, 5]。
要算 nums[1..2]（即 [−1, 3]）的和：preSum[3] − preSum[1] = 4 − 2 = 2。

哈希表怎么把查找压缩到 O(1)？

不是存“下标对”，而是存“前缀和值 → 出现次数”或“前缀和值 → 首次出现下标”，取决于题目需求：

求个数（如“和为 k 的子数组有多少个”）：用 HashMap，初始 put(0, 1)，因为和为 0 的空前缀天然存在；遍历时查 preSum[i] − k 是否存在，存在就累加对应 count。
求最长长度（如“0 和 1 个数相等的最长子数组”）：把 0 换成 −1，问题转为“和为 0 的最长子数组”，用 HashMap，只在 sum 第一次出现时记录下标，后续再遇到相同 sum，用当前 i 减去 firstIndex 就得长度。
求是否存在长度 ≥2 的子数组，和能被 k 整除（Leetcode 523）：利用同余定理，只存 preSum[i] % k → 下标，且检查下标差是否 ≥2。

一个通用模板（Java）

适用于统计个数类问题（如 Leetcode 560）：

Map<integer integer> map = new HashMap();
map.put(0, 1); // 空前缀
int preSum = 0, count = 0;
for (int x : nums) {
    preSum += x;
    count += map.getOrDefault(preSum - k, 0);
    map.put(preSum, map.getOrDefault(preSum, 0) + 1);
}
return count;
</integer>

全程只遍历一次数组，每次哈希操作平均 O(1)，总时间复杂度稳定 O(N)，空间 O(N)。