【LeetCode热题100】【子串】和为 K 的子数组

题目

给你一个整数数组?nums?和一个整数?k?，请你统计并返回?该数组中和为?k?的子数组的个数?。

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

示例 1：

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

示例 2：

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

提示：

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

暴力?

直接两层循环找出所有连续子数组的和，这个时间复杂度为n2

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int answer=0;
        for(int i=0;i<nums.size();i++){
            int sum=0;
            for(int j=i;j<nums.size();j++){
                sum+=nums[j];
                if(sum==k){
                    answer++;
                }
            }
        }
        return answer;
    }
};

但是这个会超时

前缀和

考虑到存在重复对连续子数组求和，可以使用前缀和优化这个连续子数组求和，如数组1 2 3 4 5，那么前缀和就是1 3 6 10 15，任何连续子数组的和就是对应的前缀和之差，这样就可以减少求和的重复计算，实际计算时需要在前缀和数组前补个0方便做差

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int answer=0,prefix[nums.size()+1];
        prefix[0]=0;
        for(int i=0;i<nums.size();i++){
            prefix[i+1]=prefix[i]+nums[i];
        }
        for(int i=0;i<nums.size();i++){
            for(int j=i;j<nums.size();j++){
                if(prefix[j+1]-prefix[i]==k){
                    answer++;
                }
            }
        }
        return answer;
    }
};

但是还是超时

哈希优化?

其实这时候就可以想到之前做过的【LeetCode热题100】【哈希】两数之和 C++-CSDN博客

可以用哈希来优化在数组中查找和为目标值target?的两个整数的索引，因为哈希查找的时间复杂度是O（1）的

这里同样可以使用哈希查找来优化，我们的目的是想找出两个前缀和之差为k的，考虑到同一个前缀和可能存在出现多次的情况，例如 1 -1 0，k=0，这个前缀和为0的就会出现两次，因此哈希表设计key为前缀和，value为出现的次数

遍历数组元素，计算前缀和，哈希查找前缀和 - k的key是否存在，存在则说明找到了符合的前缀和，然后加上这个前缀和出现的次数

class Solution {
public:
    int subarraySum(vector<int> &nums, int k) {
        int answer = 0, prefix=0;
        unordered_map<int,int>hashMap;
        hashMap[0]=1;
        for(int x:nums){
            prefix+=x;
            if(hashMap.find(prefix-k)!=hashMap.end())
                answer+=hashMap[prefix-k];
            hashMap[prefix]++;
        }
        return answer;
    }
};