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

基于前缀和与哈希表技术，解决 LeetCode 中和为 K 及和可被 K 整除的子数组问题。核心思路是遍历数组计算当前前缀和，通过哈希表记录历史前缀和出现的次数或余数，快速判断是否存在满足条件的子数组。针对 C++ 负数取模特性，采用 (a % n + n) % n 修正余数，确保逻辑正确。

数字游民发布于 2026/2/5更新于 2026/4/183K 浏览

在这里插入图片描述

29. 和为 k 的子数组

题目链接：

560. 和为 K 的子数组 - 力扣（LeetCode）

题目描述：

在这里插入图片描述

题目示例：

在这里插入图片描述

解法（前缀和 + 哈希表）：

算法思路：

在这里插入图片描述

设 i 为数组中的任意位置，用 sum[i] 表示 [0, i] 区间内所有元素的和。想知道有多少个以 i 结尾的和为 k 的子数组，就要找到有多少个起始位置为 x1, x2, x3...，使得 [x, i] 区间内所有元素的和为 k。那么 [0, x] 区间内的和就是 sum[i] - k。于是问题就变成：

找到在 [0, i-1] 区间内，有多少前缀和等于 sum[i] - k 的即可。

我们其实也不用真的初始化一个前缀和数组，因为我们只关心在 i 位置之前，有多少个前缀和等于 sum[i] - k。因此，我们仅需要用一个哈希表，一边求当前位置的前缀和，一边存下之前每一种前缀和出现的次数。

C++ 算法代码：

class Solution {
public:
    int  {
        unordered_map<, > hash;
        hash[] = ;
         sum = , ret = ;
         ( x : nums) {
            sum += x;
             (hash.(sum - k)) ret += hash[sum - k];
            hash[sum]++;
        }
         ret;
    }
};