剑指 Offer II 010. 和为 k 的子数组

• 剑指 Offer II 010. 和为 k 的子数组
• • 题目
  • 题目

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

示例 1：

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

示例 2：

输入:nums = [1,2,3], k = 3
输出: 2

提示:

1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

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

这道题和009:乘积小于k的数组的相似之处在于计算符合条件的数量。

数组中和为 k 的连续子数组的个数，开始思考用滑动窗口，但是数组中可能有负数，所以不确定在扩大窗口或者缩小窗口时，窗口的和是变大还是变小。
然后和为k的子数组，想到了前缀和,通过前缀和就相当于记录了所有子数组的和，因为两个前缀和相减就是它们之间子数组的和。

前缀和数组sum[i]=nums[0]+nums[1]+....+nums[i]
想知道[j,i]子数组的和，就可以用sum[i]-sum[j-1] = （nums[0]+nums[1]+....+nums[i]）- （nums[0]+nums[1]+....+nums[j-1]） = nums[j]+..+nums[i]
我们发现j必须从1开始，那么没办法算[0,i]子数组的和了。所以我们修改一下前缀和数组的定义sum[i] = nums[0]+nums[1]+...+nums[i-1]
所以[j,i]子数组的和sum[i+1]-sum[j]

var subarraySum = function(nums, k) {
    let len= nums.length;
    let sum = new Array(len+1);
    sum[0]=0;
    let res=0;
    for(let i=0;i
            sum[i+1] = nums[i] + sum[i];//计算前缀和
    }
    //枚举出所有的子数组
    for(let i=0;i
         for (let j = i; j < len; ++j) {
             if(sum[j+1]-sum[i]==k)res++;//依次计算以i开头的子数组相当于枚举
         }
    }
    return res;
};

效率很低，相当枚举了，计算[2,3,4]的时候并没有利用上[2,3]和的结果

第二内循环的作用:在找有一个j可以使得sum[j+1]-sum[i]==k,每找到一个j就让结果+1
—> 寻找与该前缀和差为k的前缀和个数，直接更新结果，不用去一个一个找
—> 我们可以用哈希表，在记录前缀和的同时记录该前缀和出现的次数。

题解笔记:https://leetcode.cn/problems/subarray-sum-equals-k/solution/dai-ni-da-tong-qian-zhui-he-cong-zui-ben-fang-fa-y/

var subarraySum = function(nums, k) {
    let len= nums.length; 
   // let sum = new Array(len+1);
   // sum[0]=0;
    let map = {0:1};//可能第一个数等于k
    let res=0;
    let total=0;
    for(let i=0;i
        total = nums[i] + total;
        //找与前缀和=total-k出现的次数
        if(map[total-k]){
            res+=map[total-k];//直接更新结果
        }
        if (map[total]) {//更新当前前缀的结果
            map[total]++;
        } else {
            map[total] = 1;
        }
    }

    return res;
};