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 即可