和为k的子数组

力扣上第560题

题目描述

给定一个数组 nums 跟一个 和为k 的值，找到该数组中和为 k 的连续的子数组的个数。

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

尝试

• 暴力破解, 即每个数跟与他以后的数相加 等于k，那么 res + 1

function subarraySum(nums, k) {
    let res = 0;
    for(let i = 0; i < nums.length; i++) {
        let current = nums[i];
        if(current == k) {
            res += 1;
        }

        for(let j = i + 1; j < nums.length; j++) {
           current += nums[j];
           if(current == k) {
               res += 1;
           } 
        }
    }
    return res;
}

• 滑动窗口，滑动窗口不太好处理，窗口向右扩展的时候，那其实是跟上面算法好像差不多，然后放弃了

• 看了题解，发现了一个前缀和算法

前缀和算法

• 将数组中的每一项在遍历时都加起来，然后加入到新的数组中，我们用s[i]表示
  • 定义s[0] = 0
  • s[1] = a[0]
  • s[2] = s[1] + a[1]
  • 所以得到 s[i + 1] = s[i] + nums[i]
  • 所以移动等式 nums[i] = s[i + 1] - s[i]

所以有以下代码

function subarraySum(nums, k) {
    let res = 0;
    let s = [0];

    // 多了这一层，结果更慢了
    for(let i = 0; i < nums.length; i++) {
        s[i + 1] = s[i] + nums[i];
    }

    for(let i = 0; i < nums.length; i++) {
        for(let j = i; j <= nums.length; j++) {
            if(s[j + 1] - s[i] == k) {
                res++;
            }
        }
    }

    return res
}

可以看到以上代码其实跟第一种方法是大同小异的，只是使用了前缀和的思想，但这个方法比上面那个还要慢，因为多 前缀和添加这一组循环

优化

看到题解是用前缀和还有哈希表做优化的

思想：

• 将当前前缀和的值当做哈希表的key。
• 将当前前缀和出现的次数 当做哈希表的value

具体操作如下:

• 当遍历 nums时，计算当前前缀和, 存入map
• 如果 map 中已存在 key 为 当前前缀和 - k, 因为一直遵守 【当前前缀和】-【之前求出的前缀和】 === k,
  • 那么取出哈希表的值，res += value,
• 如果 map 中， 没有当前前缀和的值
  • 那么把前缀和添加到哈希表中，值为1，
  • 如果有，那么改变哈希表的值: map[prefix]++

function subarraySum(nums, k) {
    let res = 0;
    let map = { 0:1 };
    let prefixSum = 0;

    for(let i = 0; i < nums.length; i++) {
        prefixSum += nums[i];

        if(map[prefixSum - k]) {
            res += map[prefixSum - k]
        }

        if(map[prefixSum]) {
            map[prefixSum]++
        } else {
            map[prefixSum] = 1
        }
    }
    return res
}