560. Subarray Sum Equals K

给定数组，求和为k的连续子数组的数目

暴力解法

• 时间复杂度 O(n^2)，空间复杂度O(1)
• Runtime: 992 ms, faster than 5.09%
• Memory Usage: 41.4 MB, less than 95.61%

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    let count = 0
    let len = nums.length
    for(let i = 0; i < len; i++) {
      let sum = 0
      for(let j = i; j < len; j++) {
        sum += nums[j]
        if(sum === k) count++
      }
    }
  return count
};

前缀和 + 哈希表优化

pre[i] 为 0~i 里面的所有元素和
k = pre[i] - pre[j - 1] 为 i~j 的所有元素的和
对抵消元素进行一次处理

• 时间复杂度O(n)，空间复杂度O(n)
• Runtime: 104 ms, faster than 84.15%
• Memory Usage: 47.5 MB, less than 58.33%

一次循环遍历的时候，将值写入 Set 中。Set 提供了新的数据结构 set，类似于数组，成员的值都是唯一的，没有重复的值。Set 本身是一个构造函数，用来生成 Set 数据结构。Map 类似对象，对象也可以当作键，只有对同一个对象的引用，Map 结构才将其视为同一个键。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    let map = new Map()
    let count = 0
    let pre = 0
    map.set(0, 1) // 抵消元素
    for(let item of nums) {
      pre += item
      if(map.has(pre - k)) {
        count += map.get(pre - k)
      }
      if(map.has(pre)) {
        map.set(pre, map.get(pre) + 1)
      } else {
        map.set(pre, 1)
      }
    }
  return count
};