前缀和配合哈希表可将子数组和为k的查找从o(n²)优化至o(n)：presum[i]表示nums前i个元素和，子数组和转化为presum[i+1]−presum[j]，再用哈希表统计presum[j]频次实现o(1)查询。
直接用前缀和能避开重复加法，把子数组求和从 O(n) 降到 O(1)，再配合哈希表，就能把整体时间复杂度从暴力的 O(n²) 压到 O(n)——这是工程中真正可用的解法。
前缀和怎么把“反复求和”变成“查表相减”
前缀和数组 preSum 的定义是：preSum[i] 表示原数组 nums 中前 i 个元素之和（即索引 0 到 i−1），且 preSum[0] = 0。这样一来，任意子数组 nums[j..i−1] 的和就等于 preSum[i] − preSum[j]。
比如 nums = [1, 2, 3, −3, 3]，它的前缀和是：
preSum = [0, 1, 3, 6, 3, 6]
要算 nums[0..1]（即 [1,2]）的和？→ preSum[2] − preSum[0] = 3 − 0 = 3
要算 nums[2..4]（即 [3,−3,3]）？→ preSum[5] − preSum[2] = 6 − 3 = 3
关键点：
• 不需要每次重新遍历加一遍，只做一次减法；
• 构建 preSum 只需一次 O(n) 遍历；
• 后续任意区间求和都是常数时间。
为什么单靠前缀和还不够快？哈希表来补位
目标是找所有满足 sum(nums[j..i]) == k 的子数组。用前缀和改写就是：
preSum[i+1] − preSum[j] == k → preSum[j] == preSum[i+1] − k
也就是说：遍历到位置 i+1 时，只要知道有多少个 j（j ≤ i）使得 preSum[j] 等于当前值减 k，就立刻知道新增几个合法子数组。
这时哈希表登场：
• 边遍历边记录每个前缀和值出现的次数；
• 每次算出 target = preSum[i+1] − k，查哈希表里 target 出现了几次，就累加几次；
• 初始插入 preSum[0] = 0，次数为 1（对应空前缀，支持从头开始的子数组）。
这样避免了二重循环枚举 j，把查找从 O(n) 降为 O(1) 平均时间。
实战编码要点：别踩这三类坑
实际写代码时，这几个细节容易导致结果错误或越界：
• 哈希表必须先查后插：确保 j 严格小于等于当前 i，不能把刚算出的 preSum[i+1] 提前计入，否则会匹配到自身；
• preSum 长度是 n+1：索引 0～n 共 n+1 个值，对应空前缀到全长前缀；
• 整型溢出要留意：当数组极长、数值极大时，前缀和可能超出 int 范围，Java/C++ 中建议用 long；Python 自动处理，但逻辑一致性仍需注意。
一个典型错误写法：
先 map.put(preSum[i+1], …)，再查 target → 会导致子数组长度为 0 或下标错乱。
对比暴力与优化的真实性能差异
以 n = 10⁵ 的数组为例：
• 暴力双循环：约 50 亿次加法 + 判断 → 在普通机器上运行超 10 秒；
• 前缀和 + 哈希：10⁵ 次加法 + 10⁵ 次哈希操作 → 通常在 10ms 内完成。
更关键的是可扩展性：
• 暴力法在 n=10⁶ 时基本不可用；
• 优化法处理百万级数据依然稳定，适合日志分析、实时风控、滑动窗口统计等真实业务场景。
