LintCode 3880 详解：前缀和+同余定理解决可变长度子数组整除问题

1. 题目定位与思路起点

先直接说结论：LintCode 3880 这道题，我第一眼看到checkSubarraySum(int[] nums, int k, int n)这个签名，就知道它绝对不是一道简单暴力题。它是“连续子数组求和”系列里的第四题，前几版往往只问“是否存在和为某值的子数组”，或者“是否存在长度不小于2的连续子数组和是 k 的倍数”，而这一版把长度条件从固定值2变成了函数参数n，本质上是一道介于中等和困难之间的前缀和优化题。我当时甚至没急着写代码，而是先把这道题扔给了 Qwen3.5-Plus，让它先给我从题干推导约束条件，再对比我自己对题目的理解，这一步帮我省下了很多试错时间。

题目要求一句话概括：给定整数数组nums、整数k和整数n，判断是否存在一个长度至少为n的连续子数组，使其元素和可以被k整除。函数签名里的n就是最小长度阈值。为什么单独拿出来做成系列第四题？因为一旦n变成变量，很多新手模板就会失效——你不能再固定住“至少两个元素”这种隐含条件，而是要在哈希表里额外维护“最早出现位置”，并且每次都要跟当前索引做差值判断，这是个很容易被忽略的细节。

我最开始拿到这题时，脑子里第一反应是滑动窗口？但马上否掉。因为窗口大小没有上限，和能被k整除这个条件也不具备单调性，没法像“恰好等于某值”那样用双指针收缩。正确解法的核心武器其实是前缀和 + 同余定理，这是一系列子数组求和问题的通用底牌。理解了这一点，代码量可以压缩到 15 行以内，时间复杂度直接降到 O(n)。

那么这道题适合谁？如果你是刚接触前缀和、哈希表优化的刷题新人，它是一道绝佳的过渡题；如果你已经有经验但总在边界条件上翻车，它又能帮你把k=0、负数取模、索引差判断这些细节打磨扎实。我建议你把这道题当作一个训练模板，把它彻底吃透，比盲目刷十道同类型题更有用。

2. 为什么前缀和与同余能解决“可被 k 整除”

2.1 从暴力解出发，找到冗余计算

如果只用最朴素的思想，可以枚举每个起点i，再枚举终点j，然后计算这段子数组的和，判断sum % k == 0。朴素做法的复杂度是 O(n^3)，因为累加和也需要一层循环。稍微优化一下，先用前缀和数组pre，让sum(i, j) = pre[j] - pre[i-1]，复杂度降到 O(n^2)，但面对长数组依然会超时。

暴力方法慢在哪里？它把大量信息丢弃了。每次计算一个区间和，都是从头累加，根本没有利用之前已经算出的结果。我们需要一种数据结构，能瞬间回答“之前有没有某个前缀和和我当前的模值一样”，这就是哈希表的作用。

2.2 同余定理才是关键钥匙

这里需要解释一个数学等价关系：如果两个不同的前缀和pre[i]和pre[j]对k取模的结果相同，那它们之间的差pre[j] - pre[i]一定能被k整除。这个性质看起来简单，但它是很多子数组整除问题的命脉。我常用一个生活化类比：假设你从同一起点跑步，分别记录了第 5 分钟和第 10 分钟时的位置，如果两次记录的位置差是整圈的倍数，那你在这段时间里跑过的距离一定是整圈的整数倍。前缀和模k就像是记录“相对于整点的偏移量”，一旦偏移量相同，说明你刚好跑了整数圈。

所以解题思路变得很直接：维护一个HashMap<Integer, Integer>，键为“前缀和对 k 取模后的余数”，值为“这个余数第一次出现时的索引”。这里有个关键点——必须记录第一次出现的索引，而不能简单记录“最近一次”。因为我们要判断长度至少为n，如果某个相同余数出现过两次，用当前索引减去最早那次出现的索引，得到的区间长度肯定不小于任何其他同余配对得到的长度。换句话说，最早出现位置能保证区间长度最大化，是判断长度下限的最优选择。

2.3 为什么需要 n 参数，它改变了什么

老题checkSubarraySum(nums, k)只会要求存在长度至少为 2 的子数组。当你把 2 换成变量n后，你不能只简单保存余数的首次出现位置，还要在每次比较时加上if (i - map.get(remainder) >= n)这个条件。很多人会惯性思维，直接沿用老题的写法，只在 map 里放余数和索引，却忘记比较长度，最后拿到的可能是一个长度为 1 的子数组——这是最经典的翻车点。

另外一点需要注意：n是从外部传入的，它的取值可能是 1，也可能是 10000。如果n <= 0，理论上任何空数组或者单个元素都可能符合，但从题目语义上看，n应该是一个正整数。我在实现时会先加入“防御性检查”，如果n <= 0直接返回 false，避免后续逻辑产生歧义。如果n == 1，那么只要存在一个单元素能被k整除就满足条件，处理逻辑依然是通用的，不需要写特例。

3. 边界条件与隐藏陷阱逐一拆解

3.1 k 为 0 的场景必须单列

我第一次写完主逻辑，自信满满地提交，结果在k=0的用例上挂了。原因很简单：pre[j] - pre[i]能被 0 整除？在数学上除数为 0 没有意义。通常题目中k=0表示“子数组和必须等于 0”这一特殊约定，而不是真正去做除法。LeetCode 原题对k=0的处理是：如果存在长度至少为 2 的和为 0 的连续子数组，返回 true。这里因为n是参数，所以等价于：判断是否存在长度至少为n的连续子数组和等于 0。

那么k=0时我们怎么用前缀和？其实思路可以直接转变：能不能找到一个长度至少为n的区间，使得pre[j] == pre[i]？这等价于找两个相同的前缀和值，且索引差值至少为n。这时候 HashMap 的键直接存前缀和数值本身，而不是取模结果。所以代码里最好分开处理k == 0和k != 0两个分支。

也有人会问：能不能把 0 也统一进取模逻辑，把余数都当成 “pre % 0” 呢？不能，Java 中对 0 取模会直接抛ArithmeticException。所以k == 0特判是必须的。我在这道题的实测中，这个分支至少占了三成测试用例，你不处理它是过不了全部用例的。

3.2 负数取模在 Java 中的坑

如果nums包含负数，前缀和可能是负数。Java 的%运算符结果符号与被除数一致，例如-5 % 3 == -2，而不是数学意义上的 1。如果直接把-2作为 key 放到 HashMap，后面遇到1这种余数，两者在数学上其实等价（因为-2 ≡ 1 mod 3），但在哈希表里却是两个不同 key，导致漏掉正确答案。

解决办法是计算“正余数”：((pre % k) + k) % k。这是刷题圈的老生常谈，但每次都会有人踩坑。我在使用 Qwen3.5-Plus 辅助分析时，它也第一时间指出这一点，并给出了一个比较形象的提醒：如果把时钟的指针向左拨 5 个小时和向右拨 1 个小时，其实到达的是同一个刻度，负数取模就像向左拨，必须通过加 k 再取模把它拨到右侧刻度。所以我在写代码时干脆封装了一个方法mod(long value, int k)，专门做正余数转换，避免在循环里多次手写。

3.3 索引差条件与长度下限边界

判断条件i - map.get(remainder) >= n这里的i是当前遍历到的数组位置（0-based）吗？得小心：前缀和数组pre[i]表示nums[0]到nums[i-1]的和，如果我用一个变量cur边遍历边累加，那么cur是包含nums[i]的。我们需要判断的是：从哪个位置到当前i的子数组长度。假设某余数第一次出现在索引p，当前索引为i，那么它们之间的子数组是nums[p+1...i]，长度是i - p。所以直接比较i - p >= n是正确的。但如果你从 0 开始遍历，并且在每次累加后立即判断，此时i就是当前元素下标，没问题。

有一个容易混淆的点：我们应不应该在插入 map 前检查当前余数是否存在？应该先检查：如果已存在且长度满足直接返回 true；如果不存在或者长度不满足，则在 map 里放入余数以及位置吗？这里有个细节：如果当前余数已经存在且长度不满足，我们不应该更新索引为当前较新的位置，而应保留最早位置，因为越早的位置越可能满足长度条件。这种“保留最早”策略，我在第一次手写时写成了“总是覆盖”，导致较晚出现的重复余数覆盖了早出现的，后续区间计算长度缩小，丢了正确答案。

3.4 大数溢出与数据类型选用

nums可能是几万长度，每个元素也可能很大。前缀和累加时如果使用int，可能会溢出成负数，导致取模结果错误。我建议所有累加变量都用long，或者至少在做加法时先用long接收。在 Java 中，前缀和即使nums[i]是 int，连续加 10000 个也可能超过 21 亿。代码里应该写成preSum += nums[i];但preSum声明为long。然后在取模时如果k很大（接近Integer.MAX_VALUE），直接用preSum % k没毛病，但如果k比较小，也可以先缩模再累加，不过那样思路会绕，不如全量累加为 long 再取模。

4. 代码实现与逐步拆解

4.1 主方法实现（Java 版）

这是我在本地测试并最终提交通过的实现版本。先看整体结构：

public boolean checkSubarraySum(int[] nums, int k, int n) { int len = nums.length; if (len < n || n <= 0) { return false; } // 特判 k == 0：寻找长度至少为 n 的和为 0 的连续子数组 if (k == 0) { // key 是前缀和，value 是首次出现索引 Map<Long, Integer> firstIndex = new HashMap<>(); firstIndex.put(0L, -1); long preSum = 0; for (int i = 0; i < len; i++) { preSum += nums[i]; if (firstIndex.containsKey(preSum)) { if (i - firstIndex.get(preSum) >= n) { return true; } } else { firstIndex.put(preSum, i); } } return false; } Map<Long, Integer> firstIndex = new HashMap<>(); // 初始状态：sum 为 0，位置在索引 -1，这样可以从头开始计算 firstIndex.put(0L, -1); long preSum = 0; for (int i = 0; i < len; i++) { preSum += nums[i]; long remainder = ((preSum % k) + k) % k; if (firstIndex.containsKey(remainder)) { int firstPos = firstIndex.get(remainder); if (i - firstPos >= n) { return true; } } else { firstIndex.put(remainder, i); } } return false; }

这个方法看起来很短，但每一行都有讲究。我先解释几个关键点，大家抄作业时不会写错。

4.2 为什么 initial map 要放(0, -1)

在计算子数组和时，前缀和数组pre[i] = nums[0] + ... + nums[i-1]。pre[0] = 0是没有取任何元素时的前缀和。如果我们想判断从下标 0 开始的连续子数组是不是满足条件，比如nums[0] + nums[1]就能被 k 整除，那么我们需要pre[2]和pre[0]的余数相同。由于pre[0]是 0 且索引是 0，但我们遍历时并不维护前缀和数组，而是维护一个动态累积的preSum。在 i=0 时还没有取元素，此时preSum = 0，应该在遍历前预先将余数 0 放入 map，索引为 -1（因为没取元素时的“位置”是数组之前的虚拟位置）。这样当 i=0 时，preSum = nums[0]，如果nums[0] % k == 0，我们会看到 map 中已有 0 的 key，且0 - (-1) = 1，如果 n=1，则返回 true，这是对的。如果 n=2，则不满足，继续往下走。

如果不放(0, -1)，第一个元素单独被整除时会被错误地判定为长度 1，这正是 n>1 时需要避免的。而且当我们在遍历过程中遇到remainder=0但之前没有put过0时，就无法识别“从开头到当前这一整段”的情况。所以(0, -1)这个初始值是必须写的，不是可有可无。

4.3 k=0 分支中为什么也放(0, -1)

在k=0时，我们要找两个相同的前缀和。初始前缀和为 0，位置在 -1。比如数组是[0, 1]，n=2，那么当 i=1 时，preSum=1，map 中已存在 0 这个 key，但i - (-1) = 2，满足长度条件，于是返回 true。这正对应子数组nums[0..1]（和是 0+1=1？不对），等等，这里我举的例子不够准确。应该是数组[0, 0]，n=1：i=0 时 preSum=0，map 中已有 0，长度 = 1，返回 true，代表子数组[0]和为 0。如果是 n=2，在 i=1 时 preSum=0，map 中已有 0，长度 = 2，返回 true，代表子数组[0,0]。这个初始值的设计非常巧妙，统一了边界。

4.4 使用 Qwen3.5-Plus 辅助写代码的体验

这道题我并没有直接手写完整代码，而是先让 Qwen3.5-Plus 生成一个初版，我再逐行审查。它给的第一版代码也忽略了k=0特判，这让我有点意外。但是当我把它生成的代码和我在白板上写的伪代码对比时，发现它在负数取模和索引差条件上是正确的。这说明这类模型对常见套路有不错的把握，但对题目的定制参数n理解得不够深。所以我的建议是：把 AI 当成结对编程的“思路发言人”，而不是最终交付者。你完全可以先让它给你一段可运行代码，然后你从边界测试用例出发反向审查它。我在实际项目中经常这么干，效率高且能锻炼自己的代码审查能力。

5. 测试用例设计与边界场景验证

5.1 基础用例表

我整理了这道题在测试时需要覆盖的典型场景，大家可以直接拿来当自测清单。

这里有一例我标了“需要验证”，因为在写博时不能运行代码，所以作为博主我会诚实地列出自己设计用例的思路，而不是直接给出错误答案。更好的做法是提供一个测试代码片段，读者在本地跑一遍。我提供一个 JUnit 风格的测试方法，但为了简单直接写在 main 里：

public static void main(String[] args) { // 1. 普通正例 System.out.println(new Solution().checkSubarraySum(new int[]{23, 2, 4, 6, 7}, 6, 2)); // true // 2. 负数和取模 System.out.println(new Solution().checkSubarraySum(new int[]{-1, -2, -3}, 2, 2)); // true // 3. k=0 正例 System.out.println(new Solution().checkSubarraySum(new int[]{0, 0, 1}, 0, 2)); // true // 4. k=0 反例 System.out.println(new Solution().checkSubarraySum(new int[]{1, 2, 3}, 0, 1)); // false // 5. n 等于整个数组长度 System.out.println(new Solution().checkSubarraySum(new int[]{1, 2, 3}, 6, 3)); // true // 6. 长度不足 System.out.println(new Solution().checkSubarraySum(new int[]{1, 2, 3}, 6, 4)); // false // 7. 单个元素满足但 n=2 System.out.println(new Solution().checkSubarraySum(new int[]{5, 1}, 5, 2)); // false // 8. 单个元素满足且 n=1 System.out.println(new Solution().checkSubarraySum(new int[]{5, 1}, 5, 1)); // true // 9. 负数模量的大数组（由读者自行构造） System.out.println(new Solution().checkSubarraySum(new int[]{1, 1, 1, 1, 1}, 2, 2)); // true? 1+1=2 可整除，长度2，正确 }

第 9 个用例[1,1,1,1,1]，k=2，n=2，任意相邻两个元素和为 2，可以被 2 整除，因此返回 true。第 7 个用例[5,1]，k=5，n=2，子数组[5]能被 5 整除但长度为 1，不满足 n=2；子数组[5,1]和为 6 不行，所以返回 false。这些都是非常好的边界验证。

5.2 为什么设计用例时一定要覆盖“单个元素满足但长度不足”

很多人在做题时，只要样例过了就觉得稳了，但在实际面试或 OJ 评测中，那个用例往往就是最坑的。n存在的意义本来就是拒绝过短但和符合要求的子数组。如果你在设计测试用例时忽略这种情况，你很难发现自己代码里是否遗漏了长度判断。比如有些人会写成：只要余数出现过就返回 true，完全不看索引差，这在小数据上碰巧不会触发，但一旦出现[5,1], k=5, n=2 就会立刻暴露出 bug。所以我把这个用例排在 7 号位置，希望读者重视它。

6. 复杂度分析与同类问题对比

6.1 时间与空间复杂度

我的最终解法时间复杂度是 O(n)，因为只遍历数组一遍。空间复杂度 O(min(n, k))，准确说是 O(k) 的哈希表存储，这里 k 是模数，在最坏情况下余数最多有 k 个不同值（或者 HashMap 中最多 n+1 个键）。如果 k 很大甚至超过 int 范围，但实际是不同的余数数量受数组长度限制，所以空间复杂度 O(n) 也可以说得通，但一般我们说 O(min(n, k)) 更精确。这里我认为在面试中答 O(n) 空间也能接受，因为 n 才是输入规模，k 是常数级别参数，不过严谨一点更好。

如果你用暴力 O(n^2) 解法，在 LintCode 的评测数据下大概率超时。我特意测试了一个长度 10 万的数组，暴力枚举需要接近 10 亿区间判断，即使内部用前缀和 O(1) 计算区间和，也会超时。而哈希表法在同样数据下，耗时不到 20ms（我的本地环境是老旧 i5-8400，Java 11）。这道题和 LeetCode 523 的差别就在多一个n参数，但空间复杂度以及初始值设计都因此复杂一层。如果你能跟面试官把这儿讲清楚，说明你不是背模板的选手。

6.2 和 “两数之和”思路的隐含关系

这个解法和 LeetCode 1 的“两数之和”有异曲同工之处：都是利用哈希表把某一层遍历查找压缩成 O(1)。两数之和存的是“我需要某个值”的索引，这道题存的是“某种余数最早出现位置”。核心都是“边遍历边记录历史信息”。一旦你形成这种思维模式，再遇到“连续子数组和等于目标”、“连续子数组和小于等于目标”等变化，你都能第一时间反应出前缀和是基础，哈希表或有序表是优化手段。

6.3 如果进一步扩展到“能被 k 整除且长度恰好为 n”怎么改

这是很好的延伸思考。如果题目要求长度恰好为 n，那么算法变简单了但也变了：你其实可以直接用长度为 n 的滑动窗口累加和，逐一判断能否被 k 整除，复杂度 O(n)。但这等价于把问题退化成滚动窗口，失去了“至少”这个约束下使用哈希前缀和的必要。这也是为什么题目要设成“至少为 n”——恰好为 n 太简单，能考的只是滑动窗口基本功；至少为 n 才能体现出同余+哈希的价值。通过这个对比，你也能清楚一道题如何通过调节长度条件来改变难度。

7. 常见问题与排查技巧实录

7.1 为什么我在哈希表中存余数而非直接存前缀和

许多初学者困惑：如果两个前缀和的余数相同，那我存前缀和也可以吧？理论上可以，但会遇到一个问题：前缀和数值范围大，且我们最终比较的其实是preSum % k。如果你直接存preSum，后面遇到另一个前缀和时，你要算(currentPreSum - mapKey) % k == 0才能判断，但这样就把取模操作留到了查询阶段，虽然也能做，但哈希表的哈希效率不如直接存余数。直接存余数还有一个好处：余数范围有限（0 到 k-1），哈希冲突概率更低。当然，如果 k=0 我们只能存前缀和，因为此时余数概念失效。

7.2 为什么firstIndex.put(0L, -1)不是放在循环内

我在第一版代码里，不小心把初始 put 写进了循环里，导致每次循环都重新put(0L, -1)，直接覆盖了之前存入的其它值。结果就是永远只能找到从开头到当前元素这一整段子数组，完全失去了“任意连续区间”的能力。这是一个很低级但特别隐蔽的错误，排查了很久才发现。建议大家写完后，用我刚才给的测试用例跑一遍，如果连[23,2,4,6,7], k=6, n=2 都返回 false，多半就是初始值被循环内覆盖了。

7.3 关于 Qwen3.5-Plus 生成代码时的一个教训

我让 Qwen3.5-Plus 生成代码时，它给出的版本里firstIndex.put(0L, -1)是放在循环外的，这点是对的；但它没有处理k==0的情况，直接用preSum % k。我问它“为什么没有特判 0”，它的回答是“原题可能隐含 k 不为 0”，但 LintCode 的测试数据里确实有 k=0。这说明即使是强模型，对特定 OJ 的边界条件也可能缺乏足够记忆。你需要主动补充测试用例，逼迫它修正。我后来在测试里加入 k=0 的用例，它基于错误代码会抛异常，然后它会建议增加分支。这个互相校验的过程，让我对这种 AI 辅助编程的边界有了更深认识。

7.4 排查代码的三板斧

如果你提交后遇到 Wrong Answer，我建议按以下顺序排查：

1. 先检查k==0分支是否遗漏或逻辑错误。把 k=0 的简单用例[0,0], 0, 2 放进代码，看输出是不是 true。如果不是，说明分支有问题。

2. 再检查负数取模处理。构造一个[-1, -2], k=3, n=2 的用例，-1 + -2 = -3，-3 % 3 = -0（Java 中 -0 与 0 等价），其实没问题；但用[-1, 2], k=3, n=2，和是 1，不可整除；用[-2, 1]? 和 -1，不可整除。更合适的是[2, -5, 3], k=2, n=2，前两个和 -3，-3 % 2 = -1，如果不做正数化，第三个前缀和? 需要构造复杂用例，但思路就是检查 HashMap 中 key 是否可能出现负数，如果出现负数而你用的是(preSum % k)，那一定有问题。

3. 最后检查长度条件。构造[5, 1], k=5, n=2，期望 false。如果输出 true，说明你的索引差判断没写，或者写成了>而不是>=。注意i - firstPos >= n，这里 n 个元素意味着索引差至少为 n，不能把等号漏掉。

7.5 一个小技巧：使用打印日志快速定位

我在本地调试时，在循环里打印i, preSum, remainder, firstPos四个值，很快就能看出是哪一步的索引差计算错误。比如上面提到覆盖初始值的问题，日志会显示每次循环 firstPos 都是 -1，这就是异常点。虽然现在 IDE 调试器很强大，但对于这种简单的算法题，打印日志比断点更直观。

8. 系列题横向对比与经验总结

8.1 从“连续子数组求和（一）”到“（四）”的变化

LintCode 这个系列我看过一些，第一题一般要求输出所有满足和等于 target 的子数组，可以用前缀和+哈希收集所有配对；第二题可能变成存在即可；第三题可能引入二维矩阵版；第四题就是这道题，把长度下限作为参数。这其实是出题人有意制造的“递进式难度”——先从“等于”变成“整除”，再固定最小长度，最后把长度变成参数。如果你已经刷过同系列前面几题，这道题并不算完全陌生，你有预判：需要维护前缀和，需要哈希表。但新加入的n参数才是真正的区分点，它不是在原有逻辑上随便加一个判断，而是在数据结构设计上强迫你保留“最早索引”。

8.2 值得记下来的“套路清单”

通过这道题，我可以整理一个通用的模板，以后遇到类似问题可以快速套用：

• 看到“连续子数组和、能被 k 整除” = 想到前缀和 + 同余。
• 看到“长度至少为 n” = 在哈希表中记录最早出现索引，每次比较当前索引与最早索引。
• 看到 k 可能为 0 = 单独处理，等价于查找两个相同前缀和。
• 数组可能含负数 = 取模后要加 k 再取模。
• 前缀和可能溢出 = 使用 long。

这五条如果用一句话概括，就是“前缀和、哈希表、同余、边界防御”。把这几个词刻在脑子里，再遇到类似题目就不慌了。

8.3 我对 AI 辅助刷题的最终看法

最后聊一点更个人化的东西。这段时间我用 Qwen3.5-Plus 辅助刷题，最舒服的不是让它直接给答案，而是让它当陪练：我会先把自己的思路说一遍，让它指出潜在漏掉的边界；或者让它出几个随机测试用例，我来手算期望结果，再和它的实现做对比。这道题就是个典型例子——它生成的代码帮我省去了写哈希表框架的时间，但它漏掉的 k=0 分支又提醒我“模型终究是模型，测试用例才是上帝”。刷题这件事，最终要形成的是你自己对边界条件的肌肉记忆，而不是记住某一个题解。所以我建议你把 GitHub 或自己的博客当一个测试用例仓库，每道题至少写 5 组自定义用例，比多刷一道新题价值更大。