把 O(n²) 降维打击成 O(n) 的 Prefix Sum 优化思路

遇到 LeetCode 数据规模达到 $10^5$ 的 Subarray Sum 题目，如果还习惯性地写双重循环暴力枚举，是不是直接就撞上 TLE（Time Limit Exceeded）了呢？看着满屏的报错，其实不用觉得挫败，这往往是我们需要提升对 Pattern 敏感度的最佳契机。

如果我们把问题转化一下：寻找 prefix[r] - prefix[l-1] = k，是不是意味着我们只需要在遍历过程中，去 Map 里通过 prefix[r] - k 寻找之前出现过的记录？通过引入 Hash Map 维护前缀和，复杂度会从 $O(n^2)$ 直接优化到 $O(n)$，这种 DX（Developer Experience）的提升真的非常丝滑。

代码实现逻辑如下，大家可以看看有没有注意到那个细节：

// 优化后的解法：利用 Map 记录前缀和，实现 O(n) 复杂度
function subarraySum(nums, k) {
  let map = new Map();
  map.set(0, 1); // 处理从索引 0 开始的边界情况
  let prefix = 0;
  let count = 0;
  for (const num of nums) {
    prefix += num;
    const needed = prefix - k;
    // 重点：一定要先查询 needed，再更新 Map，防止 k=0 时逻辑错乱
    count += map.get(needed) || 0;
    map.set(prefix, (map.get(prefix) || 0) + 1);
  }
  return count;
}

这里有个给新同学的小提醒：在处理负数前缀和时，强烈建议使用 Map 而不是 Plain Object，因为 Map 在处理 Key 的类型一致性上表现更稳健。如果大家在做 Array 相关的题目感到卡顿，不如试着思考一下能不能通过数学变换，把问题转化为某种累积属性的记录？