手帐 Blog

主题

复盘 · LC 560 和为 K 的子数组 ​

题目 ​

题意 ​

给整数数组 nums 和整数 k，统计有多少个连续子数组的和恰好等于 k。

  • 子数组连续；可重叠计数（如 [1,1,1]、k=2 → 2）。
  • nums[i] 可正可负可为 0，因此不能用「和增大就缩窗」的纯滑窗（和可非单调）。

边界：空结果 0；k=0、含 0 元素、负数前缀导致「同一前缀和出现多次」。

涉及算法 ​

标签一句话
前缀和sum(i..j) = prefix[j+1] - prefix[i]
哈希计数扫到 prefix，查有多少个历史前缀满足 prefix - k

教程对照：08 · 前缀和（本篇精讲题 560）。

评价我的解法 ​

今天是典型「暴力 → 能过的 O(n²) → 看答案写出 O(n)」三连，和 7/28 的 11/15 同款学习曲线。

版 1：增量枚举所有 [i,j]（TLE） ​

我的代码（摘自 index.js，主函数 + 辅助）：

javascript
function computeArr(nums, i, j) {
  let sum = 0;
  for (let n = i; n <= j; n++) {
    sum += nums[n];
  }
  return sum;
}

var subarraySum = function (nums, k) {
  let j = 0;
  let resCount = 0;
  let lastRowSum = 0;
  for (; j < nums.length; j++) {
    let lastSum = 0;
    for (let i = 0; i <= j; i++) {
      let subSum = 0;
      if (i === 0) {
        if (j === 0) {
          subSum = computeArr(nums, i, j);
        } else {
          subSum = lastRowSum + nums[j];
        }
        lastSum = subSum;
        lastRowSum = subSum;
      } else {
        subSum = lastSum - nums[i - 1];
        lastSum = subSum;
      }
      if (subSum === k) {
        resCount++;
      }
    }
  }
  return resCount;
};

对在哪：试图用「上一行和 / 左移减头」避免每个区间从头加，说明在想增量。

错/糙在哪：

  1. 仍是 O(n²) 枚举，最后一档 TLE（92/93）——和规模对不上。
  2. 状态过多（lastRowSum / lastSum / computeArr）：i===0 && j===0 还走一遍线性求和，可读性差，面试讲不清。
  3. 增量公式对了，但复杂度没降档，属于「优化常数、没换算法」。

版 2：固定起点累加（AC，慢） ​

我的代码（摘自 index2.js）：

javascript
var subarraySum = function (nums, k) {
  let count = 0;
  for (let i = 0; i < nums.length; i++) {
    let sum = 0;
    for (let j = i; j < nums.length; j++) {
      sum += nums[j];
      if (sum === k) {
        count++;
      }
    }
  }
  return count;
};

对在哪：代码干净，正确性一眼能验；93/93 通过。

糙在哪：时间约 1725ms / 13%——O(n²) 卡在通过线上。这是合法暴力，不是面试终解。

版 3：前缀和 + Map（看答案后 AC） ​

我的代码（摘自 index3.js，不含测例）：

javascript
var subarraySum = function (nums, k) {
  const map = new Map();
  map.set(0, 1);
  let count = 0;
  let curSum = 0;
  for (let i = 0; i < nums.length; i++) {
    curSum += nums[i];
    const need = curSum - k;
    if (map.has(need)) {
      count += map.get(need);
    }
    map.set(curSum, (map.get(curSum) || 0) + 1);
  }
  return count;
};

对在哪：

  1. map.set(0, 1)：覆盖「从下标 0 起整段和为 k」。
  2. 先查 curSum - k 再写入当前前缀：避免把「当前自己」误算成一对（当 k=0 时尤其关键）。
  3. 用时掉到约 17ms，复杂度到位。

糙在哪：注释写明「看了答案写的」——模板能抄通，但默写与口述（为何 prefix - k、为何先查后写）还欠合上本子再写一遍。

小结：从「枚举区间」走到「前缀差分 + 哈希计数」路径正确；欠账是不看笔记默写 map(0)=1 + 先查后写。

最佳题解 ​

与 index3 同构，略作注释化书写：

javascript
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function (nums, k) {
  const freq = new Map([[0, 1]]);
  let prefix = 0;
  let ans = 0;
  for (const x of nums) {
    prefix += x;
    ans += freq.get(prefix - k) || 0;
    freq.set(prefix, (freq.get(prefix) || 0) + 1);
  }
  return ans;
};
  • 时间 O(n)，空间 O(n)。
  • 为何更优：把「有多少个左端点使区间和为 k」变成「有多少个历史前缀等于 prefix - k」；每个右端点 O(1) 查询。含负数时滑窗失效，这套才是正道。

关联题目 ​

题为何相关
303. 区域和检索 - 数组不可变前缀和入门；08 另一道精讲
974. 和可被 K 整除的子数组前缀同余 + 哈希，560 的模运算版
1. 两数之和同一「查补数」心智：need = target - x ↔ need = prefix - k
437. 路径总和 III树上前缀和 + 哈希，同公式

一句话带走 ​

和为 K 的子数组：维护前缀和频次，答案累加 freq[prefix - k]；先查后写，并初始化 freq[0]=1。