【数组-5】560.和为K的子数组

题目描述：

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

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

示例 1：

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

示例 2：

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

解题思路：

读完这题我就是想到用双层循环遍历数组，枚举所有子数组，统计和为 k 的个数。

但是这只是暴力解法，并不是最优解，这样的时间复杂度不够好。

源代码如下：

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

复杂度分析：

• 时间复杂度：O(n²)，双重循环

• 空间复杂度：O(1)，只用了几个变量

最优解法：前缀和 + 哈希表

核心思路：

前缀和：prefix[i] 表示 nums[0] 到 nums[i] 的累加和。

那么，子数组 nums[j..i] 的和 = prefix[i] – prefix[j-1]。

我们要找的是：prefix[i] – prefix[j-1] == k，即：

prefix[j-1] == prefix[i] – k

也就是说：对于每个位置 i，我们只需要知道"之前有多少个前缀和等于 prefix[i] – k"。

用哈希表记录每个前缀和出现的次数，就能在 O(1) 时间内查到。

图解：

nums = [1, 1, 1], k = 2

结果：2 ✅

为什么初始要放 {0: 1}？

因为如果 prefix[i] 本身就等于 k，说明从数组开头到 i 的子数组和为 k，需要 prefix[j-1] = 0 来匹配。初始 {0:1} 就是处理这种情况。

代码实现：

class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> prefixCount; // 前缀和 → 出现次数
prefixCount[0] = 1; // 初始：前缀和0出现1次

int sum = 0; // 当前前缀和
int cnt = 0; // 满足条件的子数组个数

for (int num : nums) {
sum += num; // 更新前缀和

// 查找 sum – k 是否出现过
if (prefixCount.find(sum – k) != prefixCount.end()) {
cnt += prefixCount[sum – k];
}

// 把当前前缀和加入哈希表
prefixCount[sum]++;
}

return cnt;
}
};

复杂度分析：

两种方法对比：

关键点理解：

1.为什么前缀和能优化？

暴力解法的问题在于：对每个起点都要重新累加一遍。

前缀和的核心是：

子数组 nums[j..i] 的和 = prefix[i] – prefix[j-1]

所以不需要枚举所有起点，只需要记录每个前缀和出现过几次，然后对每个 i 查一下 prefix[i] – k 出现过几次，就相当于找到了所有满足条件的 j。

2.哈希表存什么？

3.为什么用 unordered_map 而不是 unordered_set？

因为同一个前缀和可能出现多次（比如数组中有负数或0），我们需要统计次数，而不是只判断是否存在。

总结：

这道题是前缀和 + 哈希表的经典入门题，掌握后可以解决很多类似的子数组问题（比如「和可被K整除的子数组」「连续数组」等）。

前缀和 + 哈希表是算法题中非常经典的一种组合技巧，专门解决“子数组/子区间”相关的问题。

下面总结这种技巧及其适用的场景：

一、核心适用特征

这类题目通常满足以下三个特征：

二、典型题型分类

类型1：求和恰好等于 k 的子数组

代表题：LeetCode 560「和为 K 的子数组」

核心公式：

prefix[i] – prefix[j-1] == k
→ prefix[j-1] == prefix[i] – k

变种：

• 和等于 k 的子数组个数

• 和等于 k 的最长子数组

• 和等于 k 的最短子数组

类型2：和可被 K 整除的子数组

代表题：LeetCode 974「和可被 K 整除的子数组」

核心公式：

(prefix[i] – prefix[j-1]) % K == 0
→ prefix[i] % K == prefix[j-1] % K

关键：哈希表存余数，而不是前缀和本身。

同类题：

• LeetCode 523「连续的子数组和」（和是 k 的倍数）

• LeetCode 1590「使数组和能被 P 整除」

类型3：0 和 1 个数相等的子数组

代表题：LeetCode 525「连续数组」

核心思路：

• 把 0 看成 -1，1 看成 +1

• 问题转化为：和为 0 的最长子数组

同类题：

• LeetCode 1124「表现良好的最长时间段」（把条件转化为 +1/-1）

类型4：前缀和 + 哈希表存"最早出现位置"

代表题：LeetCode 325「和等于 k 的最长子数组长度」（会员题）

核心思路：

• 哈希表存前缀和 → 最早出现的下标

• 对每个 i，查 prefix[i] – k 最早出现的下标 j

• 长度 = i – j

同类题：

• LeetCode 525「连续数组」

• LeetCode 1124「表现良好的最长时间段」

类型5：二维前缀和

代表题：LeetCode 304「二维区域和检索」

核心思路：

• 二维前缀和：prefix[i][j] 表示左上角到 (i,j) 的矩形和

• 但通常不用哈希表，而是用容斥原理

四、解题模板

模板1：求子数组个数

int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> prefixCount; // 前缀和 → 出现次数
prefixCount[0] = 1; // 初始条件
int sum = 0, cnt = 0;

for (int num : nums) {
sum += num;
if (prefixCount.count(sum – k)) {
cnt += prefixCount[sum – k];
}
prefixCount[sum]++;
}
return cnt;
}

模板2：求最长子数组

int findMaxLength(vector<int>& nums) {
unordered_map<int, int> prefixIndex; // 前缀和 → 最早出现的下标
prefixIndex[0] = -1; // 初始条件
int sum = 0, maxLen = 0;

for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
if (prefixIndex.count(sum)) {
maxLen = max(maxLen, i – prefixIndex[sum]);
} else {
prefixIndex[sum] = i; // 只记录最早出现的位置
}
}
return maxLen;
}

模板3：求最短子数组

与最长类似，但哈希表存最晚出现的位置（每次覆盖更新）。

五、关键细节

1. 初始值 {0: 1} 或 {0: -1}

• 求个数：prefixCount[0] = 1

• 求长度：prefixIndex[0] = -1

原因：处理"从数组开头到当前位置"的子数组。

2. 哈希表存什么？

3. 什么时候用 unordered_map vs unordered_set？

• 需要统计次数或位置 → unordered_map

• 只需要判断是否存在 → unordered_set

六、与其他方法对比

关键区别：

• 有负数 → 必须用前缀和+哈希表（滑动窗口失效）

• 全是正数 → 滑动窗口更简单

七、总结口诀

连续子数组，求和或计数；
前缀和做差，哈希表来助；
求个数存次数，求长度存下标；
初始零要加，负数也能查。