29. 和为 K 的子数组
题目描述
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续子数组的个数。
示例
输入：nums = [1,1,1], k = 2 输出：2 解释：[1,1] (索引 0-1) 和 [1,1] (索引 1-2)
解法：前缀和 + 哈希表
核心思路
设 i 为数组中的任意位置，用 sum[i] 表示区间 [0, i] 内所有元素的和。要计算以 i 结尾且和为 k 的子数组数量，本质是寻找起始位置 x，使得区间 [x, i] 的和等于 k。
根据前缀和定义： sum[x, i] = sum[0, i] - sum[0, x-1] = k 即：sum[0, x-1] = sum[0, i] - k
这意味着我们只需要在遍历到 i 时，统计之前有多少个前缀和等于当前前缀和减去 k。无需维护完整的前缀和数组，使用哈希表记录每种前缀和出现的次数即可。
C++ 实现
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> hash;
hash[0] = 1; // 初始化，处理从下标 0 开始的子数组
int count = 0;
int sum = 0;
for(int i = 0; i < nums.size(); i++) {
sum += nums[i];
if(hash.count(sum - k)) {
count += hash[sum - k];
}
hash[sum]++;
}
return count;
}
};
30. 和可被 K 整除的子数组
题目描述
给定一个整数数组 A，返回其中元素之和可被 K 整除的非空连续子数组的数目。
示例
输入：A = [4,5,0,-2,-3,1], K = 5 输出：7 解释：有 7 个子数组满足条件。
前置知识：同余定理与负数取模
同余定理
如果 (a - b) % n == 0，则 a % n == b % n。通俗来说，若两数之差能被 n 整除，则它们对 n 取模的结果相同。
负数取模处理
C++ 中负数取模结果可能为负（例如 -1 % 3 = -1）。为了保证余数为正，统一采用 (a % n + n) % n 的形式修正。
解法：前缀和 + 哈希表
核心思路
思路与上一题类似，但判断条件变为子数组和能否被 k 整除。 设 [0, i] 的前缀和为 b，[0, x-1] 的前缀和为 a。若 [x, i] 的和能被 k 整除，则 (b - a) % k == 0。 根据同余定理，这等价于 b % k == a % k。
因此，问题转化为：统计之前有多少个前缀和的余数与当前前缀和的余数相同。同样使用哈希表存储余数出现的频次。
C++ 实现
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k) {
unordered_map<int, int> hash;
hash[0] = 1; // 余数为 0 的情况初始化为 1
int count = 0;
int sum = 0;
int rem = 0;
for(auto i : nums) {
sum += i;
rem = sum % k;
// 修正负数取模结果
if(rem < 0) {
rem += k;
}
if(hash.count(rem)) {
count += hash[rem];
}
hash[rem]++;
}
return count;
}
};
总结
两道题均利用前缀和将区间和问题转化为查找问题，配合哈希表将时间复杂度优化至 O(n)。第二题的关键在于理解同余定理并正确处理负数取模场景。掌握这一模式，能高效解决大量涉及子数组求和的变体问题。