Leetcode Hot100之九：560. 和为 K 的子数组

题目

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。

示例 1：

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

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

提示：
1 <= nums.length <= 2 * 10^4
-1000 <= nums[i] <= 1000
-10^7 <= k <= 10 ^7

思路

暴力枚举的话，我们需要双重循环，外层循环左边界，里层循环子数组长度。也可以说是左右边界不固定，即我们需要枚举[0,……,i]里的所有下标j。但是如果我们知道[j,……,i]的子数组的和，就能o(1)算出[j-1,……,i]子数组的和。即这种不定区间的情况，我们一般考虑前缀和。

我们考虑sums[i]为[0,……,i]中所有数字的和，那么[j,……,i]子数组和为k的条件可以转化为sums[i]-sums[j-1]= =k，也就是说当我们遍历i的时候，我们考虑有多少个为sums[i]-k的前缀和即可。也就是sums[j-1]的出现次数。我们用个哈希表hashmap存储一个前缀和和其对应的出现次数。整数ans存储最终答案。
当我们从左到右遍历数组时，便可以一边算出前缀和，一遍更新答案。这样同时保证了j-1一定满足在i的左边。每遍历一个新的数nums[i]，我们计算出对应的sums[i]-k为多少，然后去哈希表中查看是否出现该数为键，如果出现，那么对应的值即以nums[i]为结尾的，满足和为k，左边界从下标1到下标i的子数组的个数。
此时注意，我们可能会少统计一种情况，就是以nums[i]为结尾的，满足和为k的，左边界为下标0的子数组。

为什么呢？因为sums[i]-sums[j-1]为[j,……,i]的子数组的和。而j-1最小是0，也就是说我们的边界情况只能统计到[1,……i]的子数组的和，会少了左边界为下标0的情况。
为了解决这个问题，我们将哈希表中多加一个(0,1)。这意味着：

• 当少统计的情况确实是答案的情况之一时，[0,……,i]的子数组的和刚好为k，sums[i]-k就应该是0，那么(0,1)就能补足这个情况。
• 当少统计的情况不是答案的情况之一时，[0,……,i]的子数组的和不为k，sums[i]-k也就遍历不到(0,1)，也不会多加这个情况。

java代码

第一版代码

class Solution {
    public int subarraySum(int[] nums, int k) {
       int len = nums.length;
       int[] sums = new int[len];
       int ans = 0;
       sums[0] = nums[0];
       HashMap<Integer,Integer>hashmap = new HashMap<>();
       hashmap.put(0,1);
       for(int i=0;i<len;i++){
           if(i>=1){
               sums[i] = sums[i-1]+nums[i];
           }
           if(hashmap.containsKey(sums[i]-k)) {
               ans+=hashmap.get(sums[i]-k);
           }
           int cnt = hashmap.getOrDefault(sums[i],0);
           hashmap.put(sums[i],++cnt);
       }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

效率分析

489ms，击败42.90%使用 Java 的用户。还需要继续优化。
我们发现，因为sums[i]的计算只与sum[i-1]有关，且循环是只有一遍的，边向右循环计算出sums[i]边更新答案ans，不会再回头循环或者用到sums[i]，所以我们用一个单独的变量pre来代替sums[i]

第二版代码

class Solution {
    public int subarraySum(int[] nums, int k) {
       int pre = 0;
       int ans = 0;
       HashMap<Integer,Integer>hashmap = new HashMap<>();
       hashmap.put(0,1);
       for(int i=0;i<nums.length;i++){
           pre += nums[i];
           if(hashmap.containsKey(pre-k)) {
               ans+=hashmap.get(pre-k);
           }
           int cnt = hashmap.getOrDefault(pre,0);
           hashmap.put(pre,++cnt);
       }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

效率分析

23ms，击败70.85%使用 Java 的用户。没啥继续优化的必要了。