前缀和算法实战：和为 K 的子数组与和可被 K 整除的子数组

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）。为了保证余数为正，统一采用 的形式修正。