560-和为K的子数组.md

560-和为 K 的子数组

原题 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。

输入：nums = [1,1,1], k = 2 输出：2

这里提到了一种前缀和的概念 题解参考

const subarraySum = function (nums, k) {
  let n = nums.length;
  let sum = Array.from({ length: n + 1 }, () => 0);
  for (let i = 0; i < n; i++) {
    sum[i + 1] = sum[i] + nums[i];
  }

  let ans = 0;
  for (let i = 0; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (sum[i] - sum[j] === k) {
        ans++;
      }
    }
  }

  return ans;
};

let nums = [1, 1, 1],
  k = 2;
let result = subarraySum(nums, k);
console.log(result);

优化

const subarraySum = function (nums, k) {
  let n = nums.length;
  let preSum = new Map();
  // 主要还是没明白，这里为什么要设置初始值为0的次数有1次
  // 明白了：看下面的解释
  preSum.set(0, 1);
  let res = 0,
    curr_sum = 0;

  for (let i = 0; i < n; i++) {
    curr_sum += nums[i];

    if (preSum.has(curr_sum - k)) {
      res += preSum.get(curr_sum - k);
    }
    preSum.set(curr_sum, (preSum.get(curr_sum) || 0) + 1);
  }

  console.log(preSum);

  return res;
};

let nums = [1, 1, 1],
  k = 2;
// let nums = [3, 5, 2, -2, 4, 1], k = 5
let result = subarraySum(nums, k);
console.log(result);

上面有一个重点，就是 preSum.set(0, 1)，设置了为和为 0 的时候有一次 这个是为了来为了满足当 for 循环的时候，i 为零的时候，如下图 也就是在 i = 0 的时候，sum += nums[0] 的，这时候 sum 的初始值是 0，所以这里设置了一些 和为零的时候的次数是 1