leetcode 560. 和为 K 的子数组（优质解法）

代码：

class Solution {
    public int subarraySum(int[] nums, int k) {
        int length=nums.length;
        // key 表示前缀和，value 表示个数
        HashMap<Integer,Integer> hashMap =new HashMap<Integer,Integer>();
        //默认有一个前缀和为 0 的数据，解决下标前缀和直接为 0 的特殊情况
        hashMap.put(0,1);

        int last=0; //前一个下标的前缀和
        int now=0;  //当前下标的前缀和
        int count=0;    //记录符合条件的子数组个数
        for(int i=0;i<length;i++){
            now=last+nums[i];
            int find=now-k; //计算要在哈希表中查找的前缀和
            count+=hashMap.getOrDefault(find,0);
            //将当前下标的前缀和添加到哈希表中
            hashMap.put(now,hashMap.getOrDefault(now,0)+1);
            last=now;
        }

        return count;

    }
}

题解：

? ? ? ? 本题的题意很清晰，需要统计出该数组中和为?k?的子数组的个数?

? ? ? ? 要注意题目给出的数据范围是?-1000 <= nums[i] <= 1000，所以数组中存在小于等于 0 的数据

? ? ? ? 先来思考一下本题的暴力解法，我们将所有的子数组遍历出来，统计出其中和为?k?的子数组的个数?即可，时间复杂度为 O（n^2），这是一个很大的时间复杂度，所以我们需要进行优化

? ? ? ? 本题可以用前缀和的方式来进行优化，定义一个前缀和数组 sum，sum[ i ] 代表从 0 ~ i 的数据总和，为了便于理解，我画了如下的图：

? ? ? ? 如上图，我们要统一以下标 i 为尾的符合条件的子数组个数，就需要在 0~ i -1 中找到下标 j ，使 j 到 i 之间数据和为 k，即我们要 0~ i -1 找到 j 下标使 sum[ j-1 ] = sum [ i ] - k ，找到多少个符合条件的 j 下标就代表以下标 i 为尾的符合条件的子数组个数有多少个，更简单来说就是，在 0~ i -1 中有多少个下标的前缀和 =?sum [ i ] - k ，就代表以下标 i 为尾的符合条件的子数组个数有多少个

? ? ? ? 我们可以将已经获取到的前缀和记录到哈希表中，前缀和为 key ，个数为 value，记录在 i 下标之前，各个前缀和对应的个数

? ? ? ? 以 nums = 1,2,3? k = 3 为例，i 一开始指向 0 下标，前缀和 sum[ 0 ] = 1，我们要查找的前缀和是? sum [ 0?] - k = 1 - 3 = -2，在哈希表中没有 -2 这个前缀和对应的数目，所以没有符合条件的子数组，i 向下遍历，将当前的前缀和记录到哈希表中

1????????2????????3????????????????? ? ? ? 哈希：

????????????????????????????????????????????????????????key = 1，value =1

i

????????前缀和 sum[ 1?] = 3，我们要查找的前缀和是? sum [ 1?] - k = 3 - 3 = 0，在哈希表中没有 0?这个前缀和对应的数目，但实际上现在 0~i 之间的子数组已经是满足要求的了，所以我们这里没有考虑到? sum [ i ] - k = 0 的特殊情况，所以一开始创建哈希表时就应该添加 key = 0，value =1（前缀和为 0 的下标有一个） 这个数据

? ? ? ? 此时在哈希表中就获取到了0?这个前缀和对应的数目 1 ，我们便得到以 1 下标为尾的符合条件的子数组个数为 1，将其记录到 count 中，将当前的前缀和记录到哈希表中

1????????2????????3? ? ? ? ????????????????哈希：

? ? ? ? ? i? ? ? ? ? ? ? ? ? ? ? ? ? ?????????????????key = 0，value =1

??????????????????????????????????????????????????????key = 1，value =1

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????key = 3，value =1

? ? ? ? i 继续向下遍历，??前缀和 sum[ 2?] = 6，我们要查找的前缀和是? sum [ 2?] - k = 6?- 3 = 3，在哈希表中前缀和为 3 的下标有 1 个，所以便得到以 2 下标为尾的符合条件的子数组个数为 1，将其记录到 count 中，将当前的前缀和记录到哈希表中

1????????2????????3???????????????????????? ? ? ? 哈希：

? ? ? ? ? ? ? ? ? ? i? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??key = 0，value =1

???????????????????????????????????????????????????????key = 1，value =1

???????????????????????????????????????????????????????key = 3，value =1

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?key = 6，value =1

? ? ? ? 而要获取当前 i 下标的前缀和很容易，我们在获取 i 下标的前缀和就已经知道 i - 1 下标的前缀和了，所以 sum[ i ] = sum[ i-1 ] + nums[ i ] ,提前设置好 0 下标之前前缀和为 0 即可

? ? ? ? ??