LeetCode560. 和为 K 的子数组（2024秋季每日一题 12）

本文主要是介绍LeetCode560. 和为 K 的子数组（2024秋季每日一题 12），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

示例 1：

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

示例 2：

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

提示：

$1<=nums.length<=2\ast 10^4$
$-1000<=nums[i]<=1000$
$-10^7<=k<=10^7$

---

思路：前缀和 + 哈希表

• 先遍历一遍数组求出前缀和（为了防止越界检查，下标从 1 开始）
• 对于前缀和，当 [i+1~j] 这个区间的和为 k 时，则有 s[j] - s[i]=k
• 所以 求多少个 区间和为 k，就转换成了求有多少个(i,j)(j > i) s[j] - s[i]= k
• 如果暴力枚举(i,j)的话，需要 $O(N^2)$ 的时间复杂度，可以考虑通过哈希表优化
• 在哈希表中存储 s[x] 出现的个数，当遍历到当前元素时，只需要判断 (s[j] - k) 在哈希表是否存在，存在的话，在答案 res 上加上(s[j] - k)出现的次数（因为如果， s[j] - k 在 hash表中存在，那说明至少有一个 s[i] 满足，s[j] - s[i] == k，而s[j] - k 出现的次数，就是 对于当前 j，有多少个 i 满足，[i~j] 区间的和为 k）

时间复杂度：$O(N)$

class Solution {
public:int subarraySum(vector<int>& nums, int k) {vector<int> s(nums.size() + 1, 0);for(int i = 1; i <= nums.size(); i++) s[i] += (s[i-1] + nums[i-1]);unordered_map<int, int> h;int res = 0;for(int i = 0; i <= nums.size(); i++){if(h.count(s[i] - k)) res += h[s[i] - k];h[s[i]] ++;}return res;}
};

这篇关于LeetCode560. 和为 K 的子数组（2024秋季每日一题 12）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---