前缀和哈希嵌套，O(N)求子数组和临界值

本文深入解析了如何利用前缀和与哈希表的巧妙嵌套，在仅需单次遍历、时间复杂度稳定为O(N)的前提下，高效解决各类连续子数组和的临界值问题——无论是统计和为k的子数组个数、寻找和为0的最长子数组，还是判断是否存在长度不小于2且和能被k整除的子数组，都无需任何嵌套循环；通过将子数组求和转化为前缀和相减，并借助哈希表以O(1)均摊时间完成关键值查找，该方法彻底摆脱了暴力解法O(N²)甚至O(N³)的性能瓶颈，尤其在大规模数据（如N > 10⁴）下展现出压倒性优势，是算法面试与工程实践中必须掌握的核心技巧。

直接用前缀和加哈希表，就能在 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;

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

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《前缀和哈希嵌套，O(N)求子数组和临界值》文章吧，也可关注golang学习网公众号了解相关技术文章。