LeetCode子数组倍数问题：存储余数的思路解析

咱来帮你拆解这道题的核心思路和对应的代码逻辑，这题用前缀和+哈希表的组合可以把时间复杂度降到O(n)，比暴力遍历的O(n²)高效太多了。

首先先明确题目要求：

给定一个非负整数数组和目标整数k，编写一个函数判断数组中是否存在长度至少为2的连续子数组，其和为k的倍数（即和等于n*k，n为整数）。例如，数组[23,2,4,6,7]、k=6时，输出应为True，因为子数组[2,4]长度为2，和为6。

核心思路：前缀和+同余定理 #

先搞懂两个关键知识点：

1. 前缀和：假设prefix[i]表示数组前i个元素的累加和，那么子数组nums[j..i-1]的和就等于prefix[i] - prefix[j]。
2. 同余定理：如果两个数的差是k的倍数，那么这两个数对k取余的结果相等。反过来也成立——如果两个数对k取余结果相等，它们的差一定是k的倍数。

结合题目要求，我们需要找到prefix[i] - prefix[j]是k的倍数，且子数组长度至少为2（也就是i - j >= 2，因为子数组nums[j..i-1]的长度是i-1 -j +1 = i-j）。根据同余定理，这等价于找两个前缀和prefix[i]和prefix[j]，满足：

• prefix[i] % k == prefix[j] % k
• i - j >= 2

哈希表的作用：记录余数第一次出现的索引 #

我们用哈希表来存储每个余数第一次出现时对应的前缀和索引。这样当后续遇到相同的余数时，直接计算当前索引与第一次出现的索引的差值，就能快速判断是否满足长度要求。

完整代码解析 #

假设你看到的是这个经典的C++解法：

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        // 处理数组长度小于2的情况，直接返回false
        if (nums.size() < 2) return false;
        
        unordered_map<int, int> remainderMap;
        // 初始状态：前缀和为0时，对应的索引是0
        remainderMap[0] = 0;
        int prefixSum = 0;
        
        for (int i = 0; i < nums.size(); ++i) {
            prefixSum += nums[i];
            // 计算当前前缀和对k的余数
            int remainder = prefixSum % k;
            
            // 如果余数已经在哈希表中
            if (remainderMap.find(remainder) != remainderMap.end()) {
                // 检查索引差是否>=2，满足则返回true
                if (i + 1 - remainderMap[remainder] >= 2) {
                    return true;
                }
            } else {
                // 余数没出现过，存入哈希表，记录当前前缀和的索引（i+1是prefix的索引）
                remainderMap[remainder] = i + 1;
            }
        }
        // 遍历完没找到符合条件的子数组
        return false;
    }
};

逐行拆解关键逻辑：

• 先判断数组长度，如果小于2直接返回false，因为不可能有长度至少为2的子数组。
• 初始化哈希表remainderMap，存入{0:0}——这对应前缀和为0的初始状态（还没加任何元素时的累加和）。
• 遍历数组时，不断累加得到当前的前缀和prefixSum，计算它对k的余数。
• 如果余数已经在哈希表中：
  • 计算当前前缀和的索引（i+1，因为prefixSum是前i+1个元素的和）与哈希表中存储的索引的差值，只要差值>=2，就说明存在符合要求的子数组，直接返回true。
• 如果余数不在哈希表中，就把这个余数和对应的索引存入表中——这里只存第一次出现的索引，这样能保证后续遇到相同余数时，索引差最大，更容易满足>=2的条件。

举个例子验证（题目中的示例） #

数组[23,2,4,6,7]，k=6：

1. 初始：remainderMap={0:0}，prefixSum=0
2. i=0，nums[0]=23：prefixSum=23，余数23%6=5，表中没有5，存入{5:1}
3. i=1，nums[1]=2：prefixSum=25，余数25%6=1，表中没有1，存入{1:2}
4. i=2，nums[2]=4：prefixSum=29，余数29%6=5，表中已有5，对应的索引是1。计算3-1=2，满足>=2的条件，直接返回true。

完美命中题目中的[2,4]这个子数组！

内容的提问来源于stack exchange，提问作者J. Doe