问题描述

给你一个整数数组 nums 和一个整数 k，如果 nums 有一个好的子数组（长度至少为 2，且子数组元素总和为 k 的倍数），返回 true；否则返回 false。

解题思路

本题是前缀和 + 同余定理的经典应用。

核心数学原理：同余定理

若子数组 nums[i...j] 的和是 k 的倍数，则有：

1
(sum[j] - sum[i-1]) % k == 0

等价于：

1
sum[j] % k == sum[i-1] % k

这意味着：如果两个前缀和对 k 取余的余数相同，且它们对应的索引距离 ≥ 2，则它们之间的子数组和就是 k 的倍数。

算法步骤

  1. 初始化哈希表：将 (0, -1) 放入哈希表，表示前缀和为 0 时的索引为 -1。这是为了处理”从数组开头开始的子数组”的情况（如 [6, 6] 且 k=6）。

  2. 遍历数组，维护前缀和：

    • 累加当前元素到 runningSum
    • 计算 remainder = runningSum % k
    • 注意处理 k == 0 的特例：直接取 runningSum 作为余数（即两个相同的前缀和才满足条件）
    • 处理负数余数：如果 remainder < 0，加上 k 使其变为正数（例如 Java 中 -1 % 6 = -1，需要变为 5）

  3. 检查哈希表：

    • 如果当前余数已经在哈希表中出现过，说明存在两个位置的前缀和余数相同
    • 检查两个位置的距离 i - map.get(remainder) 是否大于 1（确保子数组长度 ≥ 2）
    • 如果距离 ≥ 2，返回 true
    • 如果余数不在哈希表中，将 (remainder, i) 存入

举例说明

示例 1：nums = [23, 2, 4, 6, 7], k = 6

i num runningSum remainder (mod 6) map 操作
- - - - {0: -1} 初始化
0 23 23 5 {0:-1, 5:0} 5 不在 map 中，存入
1 2 25 1 {0:-1, 5:0, 1:1} 1 不在 map 中，存入
2 4 29 5 - 5 在 map 中！检查距离：2 - 0 = 2 > 1，返回 true

子数组 [2, 4] 的和为 6，是 k=6 的倍数，长度为 2。

示例 2：nums = [23, 2, 6, 4, 7], k = 6

i runningSum remainder map 操作
- - - {0: -1} 初始化
0 23 5 {0:-1, 5:0} 存入
1 25 1 {0:-1, 5:0, 1:1} 存入
2 31 1 - 1 在 map 中！距离：2-1=1，≤1，不满足，不更新 map
3 35 5 - 5 在 map 中！距离：3-0=3 > 1，返回 true

子数组 [2, 6, 4] 的和为 12，是 k=6 的倍数，长度为 3。

关键细节

  • 为什么 map 只存余数首次出现的位置？ 因为我们希望子数组尽可能长，但更重要的是”存在至少一个”。存最早出现的位置能最大化距离，更容易满足长度 ≥ 2 的条件。如果余数重复出现，不需要更新 map。
  • 为什么要有 (0, -1)？ 考虑 nums = [6], k = 6。runningSum = 6, remainder = 0。0 在 map 中（索引 -1），但 0 - (-1) = 1，不满足长度条件。而 nums = [6, 6], k = 6 时，第二个 6 的余数也是 0，1 - (-1) = 2 > 1，返回 true。

复杂度分析

  • 时间复杂度：O(n)，只需遍历数组一次，每次哈希表查找和插入都是 O(1)。
  • 空间复杂度：O(min(n, k))，哈希表中最多存储 min(n, k) 个不同的余数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package code.J523;

import java.util.HashMap;
import java.util.Map;

public class J523 {
    public boolean checkSubarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int runningSum = 0;
        for (int i = 0; i < nums.length; i++) {
            runningSum += nums[i];
            int remainder = (k == 0) ? runningSum : runningSum % k;
            if (remainder < 0) remainder += k;
            if (map.containsKey(remainder)) {
                if (i - map.get(remainder) > 1) return true;
            } else {
                map.put(remainder, i);
            }
        }
        return false;
    }
}