【每日一题】 和为 K 的子数组

题目描述

---

560. 和为 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

题解

---

前缀和 + 哈希表优化

如 nums 为 1 2 3 4 5 6
前缀和： 1 3 6 10 15 21

只需要一个数 pre 维护当前的前缀和。
如遍历到6的时候我们pre 为21，但是此时已经用哈希表存储了前缀的值和次数，假设我们k = 11，就可以通过哈希表查找 pre - k ，即 10是否存在哈希表，且存在几次。同理，我们就遍历一遍nums数组，实际上就对每一个元素都进行了前缀集合当中的查找，时间复杂度为O(N)。

class Solution {
public:
//pre 维护的是nums[0~i]的值，um维护的是数值到下标的映射，就是子数组的和
//pre - k 获得需要的值，从um当中找有多少个前缀满足.
    int subarraySum(vector<int>& nums, int k) {
        int pre = 0;
        unordered_map<int,int> um;//值和次数的映射
        int count = 0;
        um[0] = 1;
        for(int i = 0;i < nums.size() ;++i)
        {   
            pre += nums[i];//维护到i的数组和
            auto it = um.find(pre - k); //计算当前是否有满足的前缀
            //cout << pre - k << " ";
            if(it != um.end()) count += it->second; // 若有，则count 加上满足的前缀数量
            //cout << pre << endl;
            um[pre]++;//维护前缀和
        }

        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

end

• 喜欢就收藏
• 认同就点赞
• 支持就关注
• 疑问就评论