线性动态规划：统计和可被 K 整除的子数组个数（Subarray Sums Divisible by K）
字数 2447 2025-12-23 10:15:05

线性动态规划：统计和可被 K 整除的子数组个数（Subarray Sums Divisible by K）

题目描述
给定一个整数数组 nums 和一个整数 k，请返回该数组中和可被 k 整除的连续子数组的个数。

示例 1：
输入：nums = [4,5,0,-2,-3,1]，k = 5
输出：7
解释：有 7 个子数组的和可被 5 整除：
[4,5,0,-2,-3,1]、[5]、[5,0]、[5,0,-2,-3]、[0]、[0,-2,-3]、[-2,-3]。

解题思路
这是一个典型的“前缀和+同余定理”结合动态规划思想的题目。核心是：子数组和能被 k 整除 ⇔ 前缀和对 k 的余数相等。
设前缀和数组 prefix[i] = sum(nums[0..i-1])，则子数组 nums[i..j] 的和 = prefix[j+1] - prefix[i]。
能被 k 整除意味着 (prefix[j+1] - prefix[i]) % k == 0，即 prefix[j+1] % k == prefix[i] % k。
所以，问题转化为：统计前缀和数组对 k 取余后，每个余数出现的次数，并从中任选两个相同余数对应的前缀，就得到一个满足条件的子数组。

步骤详解

  1. 定义前缀和与同余映射
    为了方便计算，我们定义：

    • prefix_sum 表示累加到当前元素的前缀和。
    • remainder_count 是一个哈希表（或数组），键是前缀和对 k 的余数，值是该余数出现的次数。
    • 注意：初始时，前缀和为 0 的情况对应一个空子数组，其余数为 0，所以先记录 remainder_count[0] = 1。

  2. 遍历数组计算前缀和
    对每个位置 i，更新前缀和：
    prefix_sum += nums[i]
    然后计算当前前缀和对 k 的余数。由于数组可能包含负数，而负数的余数在编程语言中可能为负，我们需要将其映射到 [0, k-1] 的正余数范围。
    公式为：
    remainder = ((prefix_sum % k) + k) % k
    这确保了余数始终在 0 到 k-1 之间。

  3. 统计可被子数组数量
    如果某个余数之前已经出现过 t 次，那么当前前缀和可以与之前每一个该余数的位置形成一个满足条件的子数组。
    所以，当遇到一个余数 r 时：

    • 将 remainder_count[r] 的当前值累加到答案中（表示新增的子数组个数）。
    • 然后将 remainder_count[r] 加 1，记录当前余数出现次数。

  4. 为什么是动态规划？
    虽然代码看起来是简单的遍历统计，但其本质是线性动态规划的思想：

    • 状态：dp[i] 可以定义为以 i 结尾的、和可被 k 整除的子数组个数。但更高效的方法是用前缀和余数的频率来“累积”答案，避免了显式存储每个位置的 dp 值，是一种空间优化的动态规划。

实例推演
以 nums = [4,5,0,-2,-3,1]，k = 5 为例：

索引 i nums[i] prefix_sum 余数 r remainder_count[r] 之前 新增子数组数 更新后的 remainder_count
初始 - 0 0 1（初始） 0 {0:1}
0 4 4 4 0 0 {0:1, 4:1}
1 5 9 4 1 1 {0:1, 4:2}
2 0 9 4 2 2 {0:1, 4:3}
3 -2 7 2 0 0 {0:1, 4:3, 2:1}
4 -3 4 4 3 3 {0:1, 4:4, 2:1}
5 1 5 0 1 1 {0:2, 4:4, 2:1}

累加新增子数组数：0+1+2+0+3+1 = 7，与示例输出一致。

代码实现（Python 示例）

def subarraysDivByK(nums, k):
    remainder_count = {0: 1}  # 初始化，余数0出现1次
    prefix_sum = 0
    ans = 0
    for num in nums:
        prefix_sum += num
        remainder = prefix_sum % k
        # 处理负数情况
        if remainder < 0:
            remainder += k
        # 当前余数之前出现的次数即为新增的子数组数
        ans += remainder_count.get(remainder, 0)
        # 更新该余数出现次数
        remainder_count[remainder] = remainder_count.get(remainder, 0) + 1
    return ans

复杂度分析

  • 时间复杂度：O(n)，只需要遍历数组一次。
  • 空间复杂度：O(min(n, k))，哈希表最多存储 k 个不同的余数。

关键点总结

  1. 利用前缀和将子数组和转化为前缀和之差。
  2. 利用同余定理将整除判断转化为余数相等判断。
  3. 动态规划（或累积统计）思路：每遇到一个重复的余数，就新增若干个子数组。
  4. 注意负数取余的处理，要统一映射到非负范围。

这个题目结合了前缀和、同余性质和动态规划的累计思想，是解决“子数组和与整除相关”问题的经典模版之一。

线性动态规划：统计和可被 K 整除的子数组个数（Subarray Sums Divisible by K） 题目描述 给定一个整数数组 nums 和一个整数 k ，请返回该数组中和可被 k 整除的连续子数组的个数。 示例 1： 输入：nums = [ 4,5,0,-2,-3,1 ]，k = 5 输出：7 解释：有 7 个子数组的和可被 5 整除： [ 4,5,0,-2,-3,1]、[ 5]、[ 5,0]、[ 5,0,-2,-3]、[ 0]、[ 0,-2,-3]、[ -2,-3 ]。 解题思路 这是一个典型的“前缀和+同余定理”结合动态规划思想的题目。核心是： 子数组和能被 k 整除 ⇔ 前缀和对 k 的余数相等 。 设前缀和数组 prefix[i] = sum(nums[0..i-1]) ，则子数组 nums[i..j] 的和 = prefix[j+1] - prefix[i] 。 能被 k 整除意味着 (prefix[j+1] - prefix[i]) % k == 0 ，即 prefix[j+1] % k == prefix[i] % k 。 所以，问题转化为：统计前缀和数组对 k 取余后，每个余数出现的次数，并从中任选两个相同余数对应的前缀，就得到一个满足条件的子数组。 步骤详解 定义前缀和与同余映射 为了方便计算，我们定义： prefix_sum 表示累加到当前元素的前缀和。 remainder_count 是一个哈希表（或数组），键是前缀和对 k 的余数，值是该余数出现的次数。 注意：初始时，前缀和为 0 的情况对应一个空子数组，其余数为 0，所以先记录 remainder_count[0] = 1 。 遍历数组计算前缀和 对每个位置 i ，更新前缀和： prefix_sum += nums[i] 然后计算当前前缀和对 k 的余数。由于数组可能包含负数，而负数的余数在编程语言中可能为负，我们需要将其映射到 [0, k-1] 的正余数范围。 公式为： remainder = ((prefix_sum % k) + k) % k 这确保了余数始终在 0 到 k-1 之间。 统计可被子数组数量 如果某个余数之前已经出现过 t 次，那么当前前缀和可以与之前每一个该余数的位置形成一个满足条件的子数组。 所以，当遇到一个余数 r 时： 将 remainder_count[r] 的当前值累加到答案中（表示新增的子数组个数）。 然后将 remainder_count[r] 加 1，记录当前余数出现次数。 为什么是动态规划？ 虽然代码看起来是简单的遍历统计，但其本质是 线性动态规划 的思想： 状态： dp[i] 可以定义为以 i 结尾的、和可被 k 整除的子数组个数。但更高效的方法是用前缀和余数的频率来“累积”答案，避免了显式存储每个位置的 dp 值，是一种空间优化的动态规划。 实例推演 以 nums = [ 4,5,0,-2,-3,1 ]，k = 5 为例： | 索引 i | nums[ i] | prefix_ sum | 余数 r | remainder_ count[ r] 之前 | 新增子数组数 | 更新后的 remainder_ count | |---|---|---|---|---|---|---| | 初始 | - | 0 | 0 | 1（初始） | 0 | {0:1} | | 0 | 4 | 4 | 4 | 0 | 0 | {0:1, 4:1} | | 1 | 5 | 9 | 4 | 1 | 1 | {0:1, 4:2} | | 2 | 0 | 9 | 4 | 2 | 2 | {0:1, 4:3} | | 3 | -2 | 7 | 2 | 0 | 0 | {0:1, 4:3, 2:1} | | 4 | -3 | 4 | 4 | 3 | 3 | {0:1, 4:4, 2:1} | | 5 | 1 | 5 | 0 | 1 | 1 | {0:2, 4:4, 2:1} | 累加新增子数组数：0+1+2+0+3+1 = 7，与示例输出一致。 代码实现 （Python 示例） 复杂度分析 时间复杂度：O(n)，只需要遍历数组一次。 空间复杂度：O(min(n, k))，哈希表最多存储 k 个不同的余数。 关键点总结 利用前缀和将子数组和转化为前缀和之差。 利用同余定理将整除判断转化为余数相等判断。 动态规划（或累积统计）思路：每遇到一个重复的余数，就新增若干个子数组。 注意负数取余的处理，要统一映射到非负范围。 这个题目结合了前缀和、同余性质和动态规划的累计思想，是解决“子数组和与整除相关”问题的经典模版之一。