和为K的子数组-560

[sl1673495]

给定一个整数数组和一个整数  k，你需要找到该数组中和为  k  的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :

数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subarray-sum-equals-k
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

直接求解

不断的尝试从 0 ~ nums.length 确定一个左边界，然后分别尝试右边界 left + 1 ~ nums.length - 1，在确定左边界后这个遍历右边界的的过程中记录一个值 total，不断的增加它的值，一旦这个值和 k 相等，就把结果 res 的值加一。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
let subarraySum = function (nums, k) {
  let n = nums.length
  if (!n) {
    return 0
  }

  let res = 0
  for (let i = 0; i < n; i++) {
    let total = 0
    for (let j = i; j < n; j++) {
      total += nums[j]
      if (total === k) {
        res += 1
      }
    }
  }
  return res
}

前缀和

先提前构造好 sums 数组，sums[i] 代表数组长度为 i 的时候的和，这样求解 nums[left ~ right] 的值只需要求 sums[right + 1] - sums[left] 即可。其余的思路和上面的解法一样，由于上面的解法中也是用 total 变量不断累加而不是每次求和，所以这两种方法性能差距不大。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
let subarraySum = function (nums, k) {
  let n = nums.length
  if (!n) {
    return 0
  }

  let sums = []
  sums[0] = 0
  for (let i = 1; i <= n; i++) {
    sums[i] = sums[i - 1] + nums[i - 1]
  }

  let res = 0
  for (let left = 0; left < n; left++) {
    for (let right = left; right < n; right++) {
      let sum = sums[right + 1] - sums[left]
      if (sum === k) {
        res += 1
      }
    }
  }
  return res
}

[vortesnail]

一次遍历即可：

var subarraySum = (nums, k) => {
    let count = 0;
    let prefixSum = 0;
    const map = Object.create(null);
    map[0] = 1;

    for (let i = 0; i < nums.length; i++) {
        prefixSum += nums[i];
        if (map[prefixSum - k] > 0) {
            count += map[prefixSum - k];
        }
        if (map[prefixSum] > 0) {
            map[prefixSum]++;
        } else {
            map[prefixSum] = 1;
        }
    }

    return count;
};

[keer-tea]

一次遍历即可：

var subarraySum = (nums, k) => {
    let count = 0;
    let prefixSum = 0;
    const map = Object.create(null);
    map[0] = 1;

    for (let i = 0; i < nums.length; i++) {
        prefixSum += nums[i];
        if (map[prefixSum - k] > 0) {
            count += map[prefixSum - k];
        }
        if (map[prefixSum] > 0) {
            map[prefixSum]++;
        } else {
            map[prefixSum] = 1;
        }
    }

    return count;
};

没看懂呀，能不能解释以下