【每日一题】 和为 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;
}
};
end
- 喜欢就收藏
- 认同就点赞
- 支持就关注
- 疑问就评论