leetcode560题解【前缀和+哈希】

leetcode560.和为K的子数组

题目链接

算法

前缀和+哈希

时间复杂度O(n)。

在解决这道题前需要先清楚，一个和为k的子数组即为一对前缀和的差值【这句话摘自链接】

1.我们假设有这么一个子数组[i,j]满足数字和为k，那么就有pre[j] - pre[i-1] = k（注:pre数组为记录前缀和的数组），则pre[i-1] = pre[j] - k；

2.题目问找到nums数组中和为k的连续的子数组的数目,一开始想到是否会重叠，后来仔细看题目后发现题目中并没有限定子数组是否重叠，那么这道题只需要记录pre[i-1]出现的次数即可；

3.不过为什么要累加pre[i-1]出现的次数呢?

原因是我们要算出满足以下标为j为结尾的数组的数字和为k的出现的次数,由pre[i-1] = pre[j] - k可知[i,j]这个子数组已经满足数字和为k,那么首先需要想到的是应该把这一次记录上,即+1,不过由于在遍历时我们每次都会把当前的前缀和用一个哈希表存储下来,并且累加1,这里我们每次都累加1,也就是说在下标i前面有可能存在一个下标k,满足[k,i]这个子数组的数字和为k,这样就不难理解为什么每次都需要累加pre[i-1]的次数了.(注意这个pre[i-1]的值是通过pre[j]-k来得到的)

4.如果还没理解为什么要累加pre[i-1]出现的次数，来张图感受一下。

观看上图，假设我们已经知道OA、OB、OC的长度均为s，那么我们可取距离C点为k的点D，可知AD=BD=CD=k，通过这个图就很好理解为什么要累加pre[j]-k出现的次数了。

5.这道题当初做的时候理解错题目了,原以为是求出连续的符合条件的子数组，并且子数组之间边界恰好重叠。其实这道题说的是这个子数组连续,也就是说这个子数组它不间断,否则没有理解到这点就很难做对了。

C++代码

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int len = nums.size();
        int sum = 0;        //记录当前位置的前缀和
        int res = 0;
        unordered_map<int,int> hs;
        hs[0] = 1;      //表示和为0出现1次
        for(int i = 0; i < len; i++){
            sum += nums[i];
            if(hs.find(sum - k) != hs.end()){
                res += hs[sum-k];
            }
            hs[sum]++;
        }
        return res;
    }
};