前缀和-560.和为k的子数组-力扣(LeetCode)

一、题目解析

1.子数组是数组中元素的连续非空序列

2.nums[i]范围为[-1000,1000]，存在负数

3.由于2的题目条件，该题不能用双指针算法，不具备单调性 

二、算法原理

解法1：暴力解法->枚举 O(N^2)

固定一个值，向后枚举数组和，遇到sum == k仍需继续枚举，因为后面同样有可能出现sum == k的情况

解法2：前缀和+哈希表

用哈希表unordered_map<int,int> hash，统计前缀和出现的频率

细节问题：

1.前缀和加入哈希表的时机？

在判断hash表中是否存在sum[i]-k后加入哈希表，即在下一个位置计算前缀和时，哈希表内存储的是上次的前缀和，也就是[0,i-1]区间的前缀和

2.不用真的创建一个前缀和数组，使用变量sum标记前一个位置的前缀和

3.如果整个前缀和等于k呢？

即在hash中，hash[0]=1

三、代码示例

class Solution {
public:
    int subarraySum(vector<int>& nums, int k)
    {
        unordered_map<int,int> hash;
        hash[0] = 1;
        int sum = 0,ret = 0;
        for(auto e : nums)
        {
            sum += e;
            if(hash.count(sum - k)) ret += hash[sum - k];
            hash[sum]++;
        }
        return ret;
    }
};

看到最后，如果对您有所帮助，还请点赞、收藏和关注，我们下期再见！