和为 K 的子数组

和为 K 的子数组问题如何转化为前缀和？

• 原问题: 统计有多少对 (i, j) 使 nums[i..j] 的和等于 k;
• 前缀和形式: prefixSum[j+1] - prefixSum[i] = k;
• 即对每个 j, 统计前面出现过多少次 prefixSum[j+1] - k;
• 这与两数之和思路一致, 用哈希表把查找降为 O(1);

如何用哈希表实现？

• 映射: 前缀和 -> 出现次数;
• 初始化 { 0: 1 }, 登记空前缀, 使从下标 0 开始的子数组也被统计;
• 遍历时先累加当前前缀和, 再把 当前前缀和 - k 的出现次数累加进结果, 最后登记当前前缀和;

function subarraySum(nums: number[], k: number): number {
  const count: Record<number, number> = { 0: 1 };
  let res = 0;
  let sum = 0;
  for (const num of nums) {
    sum += num;
    res += count[sum - k] ?? 0;
    count[sum] = (count[sum] ?? 0) + 1;
  }
  return res;
}

不用哈希表时复杂度是多少？

• 双重循环枚举左右端点, 用前缀和差值求和: 时间 O(n^2), 空间 O(n);
• 用哈希表: 时间 O(n), 空间 O(n) (最坏情况下每个前缀和各不相同);