第一次在题库里看到“Qwen3.5-Plus LintCode 3880.连续子数组求和四”这个题目标题时我愣了一下——前面那串字符看着像某个大模型自动生成的占位符。点开方法签名public boolean checkSubarraySum(int[] nums, int k, int n)才反应过来这是一道典型的连续子数组求和变体题而且比大家熟悉的 LeetCode 523 多了一个参数n。多一个参数看起来只是把“长度至少为2”变成“长度至少为n”但实现时的边界逻辑和 HashMap 的维护策略会绕晕不少人。这篇文章我会把这道题完整拆一遍n到底是什么意思、为什么前缀和加同余定理能优化到 O(n)、HashMap 里该存什么不该存什么、有哪些刷题时容易翻车的坑最后聊几句面试官可能追问的变体。适合正在刷 LintCode/LeetCode 准备面试的 Java 同学也适合刚学完前缀和想巩固同余定理的开发者。如果你已经能独立写出 LeetCode 523可以直接跳到第 4 节看n参数带来的差异如果是第一次接触这类题建议从头顺序读。1. 题目变体到底改了什么从固定长度2到参数n1.1 先回顾LeetCode 523的原始定义LeetCode 523 的checkSubarraySum(int[] nums, int k)要求判断数组中是否存在一个长度至少为 2 的连续子数组其和能够被k整除。注意这里“长度至少为2”不是随便定的。它是为了排除一种平凡答案单个元素本身就是k的倍数。比如nums[3], k3单个元素 3 显然满足“是 3 的倍数”但题目考察的是连续子数组之间的组合关系所以要强制至少两个元素。一旦把长度下限从 2 换成参数n题目的难度层级就变了n1时允许单元素直接命中n2时就是原题n很大时可能答案根本不存在需要提前做长度判断。1.2 第三个参数n到底代表什么我的理解是n表示“连续子数组的最短长度”即要求存在一个长度至少为n的子数组且它的和是k的倍数。这是这道题区别于原版的核心变量也是整个解法的约束条件。看几个具体例子nums[23,2,4,6,7], k6, n2子数组[2,4]长度为 2和为 66 能被 6 整除返回true。nums[23,2,4,6,7], k6, n3子数组[2,4,6]长度为 3和为 1212 能被 6 整除返回true。nums[1,2], k3, n3整个数组长度只有 2小于n直接返回false。其实这里有一个隐含条件值得注意n是“长度下限”不是“恰好长度为 n”。面试时如果题面不够清晰第一件事就是和面试官确认这个定义。我见过有人把n理解成“和为 k 的 n 倍”也有人理解成“第 n 个子数组”整个解法方向都会偏掉。链式连续的“连续子数组求和四”这种命名大概率是系列题前面的一二三分别改过不同的约束最后一版把长度参数化很符合这类题目演进的套路。1.3 方法签名里能读出的隐藏约束返回值是boolean说明只要判断“存在性”不需要返回子数组本身。这降低了实现难度但面试官如果追问“返回子数组怎么办”你就得提前想好额外信息怎么存。参数只有nums、k、n三个说明算法应该尽量原地处理不要修改原数组。HashMap、HashSet 这类辅助结构是允许的因为这是在线判题不是极简内存环境下的嵌入式题。还有一个容易忽略的点输入数组可能为 null可能为空可能长度小于nk可能为 0、为负数。这些边界情况很多题解不会写但真正面试手写时面试官就喜欢在这些地方挑毛病。2. 前缀和与同余定理为什么O(n)解法成立2.1 前缀和是一本累计账本前缀和可以理解成“累计账本”。我定义一个preSum[i]表示数组前i个元素的总和也就是nums[0]到nums[i-1]的和特别地preSum[0]0。为什么要把空数组对应到 0因为这样定义能让后续公式特别干净nums[l..r]的和 preSum[r1] - preSum[l]。打个比方想知道从 15 号到 25 号一共花了多少钱只需要用“25 号的累计花销”减去“14 号的累计花销”不用真的去翻每天的小票。2.2 子数组求和公式一步到位nums[l..r]的和 preSum[r1] - preSum[l]这个公式里的1是新手最容易错的地方。举个例子nums[3,1,2]前缀和数组为preSum[0,3,4,6]。子数组[1,2]下标从 1 到 2的和就是preSum[3] - preSum[1] 6 - 3 3。如果你写成preSum[2] - preSum[1]就会少算nums[2]。这种下标错位在生产代码里可能只是多调半天但在在线判题里就是 invisible 的 WA。所以后面所有代码我都采用“前缀索引”这个概念preSum[i]对应的不是元素下标i而是“前 i 个元素”。写循环时务必小心这个偏移。2.3 同余定理不看差值只看余数判断“两个前缀和的差能被k整除”有一个非常关键的等价关系如果A % k B % k那么(A - B) % k 0。反过来也成立。这就是同余定理。这个定理是整个 O(n) 解法的支点我们不需要真正去计算每个子数组的和只需要维护“前缀和对k取模后的余数是否重复出现过”。如果两个前缀索引i和ji j的余数相同那么它们中间夹着的子数组nums[i..j-1]的和一定是k的倍数。这个思路有点像“找朋友”两个不同时间点的账本余额除以同一个数之后余数一样那说明这段时间内的收支总和刚好能被这个数整除。你不需要知道中间每一笔到底是多少只要知道两头余数一样就够了。2.4 把长度限制翻译成索引差长度约束也要翻译到前缀索引空间里。前缀索引i和j对应子数组nums[i..j-1]这个子数组的长度是j - i。所以“长度至少为 n”就变成了j - i n。于是整个问题最终转化为是否存在两个不同的前缀索引i j满足preSum[i] % k preSum[j] % k并且j - i n。这一步翻译非常关键。它说明了几件事哈希表的 value 必须保存“最早出现该余数的前缀索引”因为最早的索引才能让后续的j减去它时产生足够大的长度。如果同一个余数反复出现我们不能简单地覆盖旧值否则会把“最早位置”弄丢。3. 从暴力到HashMap三段式复杂度演进与选型理由3.1 暴力三重循环逻辑最直走得最慢最朴素的思路是枚举起点l、终点r再对[l,r]求和验证。三重循环时间复杂度 O(n^3)空间复杂度 O(1)。如果数据量很小比如长度不超过 100暴力写起来很快也不需要动脑。但“连续子数组求和”这类题目的数据规模从来不给暴力机会一旦nums长度到 10^5 级别O(n^3) 基本就是超时预定。这个方案存在的意义主要是帮助理解题意以及作为小数据对拍的基准实现。3.2 前缀和加双重循环用空间换时间的第一步先用 O(n) 时间算出前缀和数组再枚举起点l和终点r通过preSum[r1] - preSum[l]O(1) 求出子数组和。循环两层时间复杂度 O(n^2)空间复杂度 O(n)。这个方案在数据规模中等时可以运行但还不够。因为枚举起终点本质上还是在遍历所有子数组只是把“求和”这一步优化掉了。真正要突破 O(n^2)必须放弃“枚举所有子数组”这个思路改从数学关系入手。3.3 HashMap同余法为什么必须用“余数”做线索HashMap 同余法只需要一遍扫描。具体策略是遍历前缀索引j维护一个MapLong, Integerkey 是“当前前缀和对k取模后的余数”value 是“这个余数第一次出现时对应的前缀索引”。每到一个新的前缀索引j先查一下 Map 里有没有相同余数如果有说明存在一个更早的前缀索引i它们的差值能被k整除也就是nums[i..j-1]的和是k的倍数。此时再判断j - i n如果满足就直接返回true。如果不满足长度约束不能急着更新 Map必须保留最早的索引。如果 Map 里没有这个余数就把当前j作为该余数第一次出现的位置存进去。这里为什么用 HashMap 而不是数组因为余数的值域由k决定k可以很大、可以为负数、甚至可以为 0哈希表不受值域限制是更通用的选择。JDK 的 HashMap 对散列冲突做了红黑树优化最坏情况也不会太差常规场景下可以认为是常数级别。3.4 三种方案放在一起看方案时间复杂度空间复杂度核心思想适用场景暴力三重循环O(n^3)O(1)全部枚举再求和极小规模一般只用来对拍前缀和 双重循环O(n^2)O(n)用前缀和公式快速求子数组和中等规模数据HashMap 同余法O(n)O(n)只看余数是否重复出现大规模数据比赛和面试的标准解空间复杂度的 O(n) 是最坏情况。实际上 Map 里的 key 数量不会超过理论上的余数种类数k和前缀索引数n1所以界是 O(min(n, k))写题解时统一写 O(n) 就行。4. HashMap实现的关键顺序先查后存与最早索引4.1 可直接运行的Java实现先放完整代码注释写在关键位置import java.util.HashMap; import java.util.Map; public boolean checkSubarraySum(int[] nums, int k, int n) { if (nums null || n 0 || nums.length n) { return false; } long kk Math.abs((long) k); if (kk 0) { return checkZeroSum(nums, n); } // key前缀和对kk取模后的非负余数 // value该余数第一次出现时的前缀索引 MapLong, Integer firstPos new HashMap(); firstPos.put(0L, 0); long preSum 0L; for (int j 1; j nums.length; j) { preSum nums[j - 1]; long mod ((preSum % kk) kk) % kk; Integer pos firstPos.get(mod); if (pos ! null) { if (j - pos n) { return true; } } else { firstPos.put(mod, j); } } return false; } private boolean checkZeroSum(int[] nums, int n) { MapLong, Integer firstPos new HashMap(); firstPos.put(0L, 0); long preSum 0L; for (int j 1; j nums.length; j) { preSum nums[j - 1]; Integer pos firstPos.get(preSum); if (pos ! null j - pos n) { return true; } firstPos.putIfAbsent(preSum, j); } return false; }代码看起来不长但每一行都有讲究。下面拆开讲几个最容易出错的设计决策。4.2 “先查后存”决定了正确性这段代码的核心顺序是先查 Map 里有没有相同余数再决定是否写入。为什么不能反着来如果先把自己写进去再查第一次遇到某个余数时查到的就是自己索引差为 0永远满足不了n 1的长度约束等于把所有真正的匹配都挡在了外面。更隐蔽的错误是同一个余数已经存在时不能把 value 更新成更大的索引。Map 里保存的必须是“最早出现位置”因为最早的索引与未来任意j的差值最大最容易满足长度约束。一旦覆盖成更大的索引本来能满足条件的答案可能就漏掉了。这里可以直观理解成“占座位”同余的余数就像同一个班号最早来的人坐在最前面后来的人都得往后排。只有最前面那个人的位置才能让队伍拉出足够长的距离。把最早的位置让给别人后面的距离全都不够了。4.3 初始化put(0,0)是在给“从头开始的子数组”留位置firstPos.put(0L, 0)这一行经常被忽略但它负责捕获那些从数组开头开始的合法子数组。preSum[0]0意思是“空前缀”在索引 0 的位置出现过。后面遍历到某个j时如果preSum[j] % k 0并且j - 0 n说明从数组开头到j-1这个子数组的和能被k整除。举个例子nums[2,1], k3, n2。遍历到j2时preSum33 % 3 0Map 里余数 0 的最早索引是 02-0 2成立所以返回true。子数组[2,1]长度为 2和为 3完全合法。如果没有这一行初始化从数组开头开始的子数组就永远没机会被判定这类边界用例必然 WA。4.4 n1和n2退化时如何验证写完代码之后最好自己先验证两个退化场景。n1例如nums[4], k4, n1。遍历到j1时preSum44 % 4 0Map 里余数 0 的索引是 01-0 1返回true。单元素[4]长度 1和能被 4 整除正确。n2退化成 LeetCode 523。很多 523 题解里写的是map.put(0, -1)然后从i0开始遍历。这和我这里的map.put(0, 0)、从j1开始遍历本质上是同一套逻辑只是前缀索引的定义方式不同。为什么会有-1的写法因为那类题解把“当前元素位置”放在遍历下标i上用i - map.get(mod) 2判断初始值为-1是为了让i0时差值刚好是 1能排除单元素。两种写法都能跑通但必须理解自己用的是哪种索引约定别混着抄。5. 刷题中会踩的连环坑取模归一化与k0边界5.1 Java取模和数学取模是两回事Java 的%运算在遇到负数时结果符号跟被除数保持一致。比如-7 % 3结果是-1而不是数学意义上的2。这会导致一个隐蔽 bug-1和2在数学上是同余的都除以 3 余数相同但在 Java 里它们是两个不同的整数HashMap 会把它们当作两个不同的 key。如果数组里出现负数直接用preSum % k做 key就可能漏掉本该匹配的子数组。解决方法是把余数归一化到[0, k-1]区间long mod ((preSum % kk) kk) % kk;如果preSum % kk是负数加上kk再取一次模就能得到非负余数。如果数组全部非负这个归一化可以省略但为了代码通用性和减少排查成本我建议一律写上。它不会拖慢程序却能在未来帮你省掉一个大坑。5.2 前缀和溢出是一个很多人忽略的点数组题目的数据规模经常到 10^5 甚至更大元素绝对值也不小int累加很容易溢出。在我这段代码里preSum用的是long这是一个非常重要的工程习惯。同理k也建议先转成long再取绝对值。因为Math.abs(Integer.MIN_VALUE)在int范围内会溢出返回的还是负数而Math.abs((long) k)能正确得到正数。这类细节在大厂面试手写时很加分因为面试官看的往往不是算法本身而是你处理边界的心智模型。5.3 k0必须单独处理如果题面允许k0取模运算就没有意义了。此时“和是 k 的倍数”这个条件退化为“子数组和为 0”。处理方式是用前缀和本身做 HashMap 的 key判断两个前缀和是否相等。如果preSum[i] preSum[j]且j - i n说明nums[i..j-1]的和恰好为 0返回true。代码里我已经写了checkZeroSum分支。如果题目明确保证k 0这个分支可以省略。但写题解的时候我倾向于保留它因为在线判题的测试用例经常会塞入边界情况来考察代码健壮性。5.4 防御性判断n和数组长度的关系代码开头有两行防御性判断if (nums null || n 0 || nums.length n) { return false; }n 0为什么返回false从数学上讲“长度至少为 0”恒为真但竞赛题不会这么出而且n作为长度下限正常情况下一定是正整数。防御性返回false可以避免后续循环里出现数组越界或死循环是一种稳妥工程习惯。nums.length n也很好理解整个数组都不够长根本不可能存在长度为n的子数组直接返回false即可省掉后面无意义的计算。5.5 一个真实debug反例覆盖最早索引之后答案消失我之前写过一个错误版本在每个余数出现时都用map.put(mod, j)更新成最新索引结果某个测试用例一直返回false。当时我还纳闷明明同一个余数出现了好几次怎么找不到答案。构造一个反例nums[1,2,3,2,3], k5, n3。前缀和依次是preSum[0]0余数 0preSum[1]1余数 1preSum[2]3余数 3preSum[3]6余数 1preSum[4]8余数 3preSum[5]11余数 1。正确版本中余数 1 第一次出现在索引 1。到j5时余数又是 15-14 3于是判定true对应子数组是nums[1..4][2,3,2,3]长度为 4和为 10能被 5 整除。错误版本里余数 1 第一次出现在索引 1到j3时被更新成索引 3再到j5时5-32 3长度不够返回false。本来能过的答案被自己亲手覆盖掉了。所以 HashMap 的写入一定要用putIfAbsent或containsKey判断。putIfAbsent是 JDK 自带的方法语义就是“只在 key 不存在时写入”非常适合这个场景。6. 面试追问与扩展一道题变成一套题6.1 追问一改成返回子数组本身如果面试官让你返回子数组本身而不是booleanMap 里那 v例如pos就是子数组的起点前缀索引实际元素起点是pos终点是j-1。直接用Arrays.copyOfRange(nums, pos, j)就能拿到结果。这意味着你需要在找到答案的瞬间记录pos和j。核心算法不变只是返回类型从boolean改成int[]或者ListInteger。6.2 追问二统计满足条件的子数组个数统计个数比判断存在性要麻烦一点因为“长度至少为 n”的约束要求你统计所有可能的索引对。我的建议是第一遍遍历用MapLong, ListInteger记录每个余数出现的所有前缀索引列表。然后对每个列表统计索引差 n的点对数。因为列表是按遍历顺序自然有序的可以用双指针维护总复杂度依然是 O(n)不会退化到 O(n^2)。这个变体在面试中很常见因为它考察的不是背代码而是能不能灵活调整数据结构来适配不同的输出要求。6.3 追问三k很大或者k为负数怎么办k很大时HashMap 的 key 种类上限是n1跟k的大小没有关系。所以时间复杂度依然是 O(n)只是散列分布更稀疏哈希表的空间利用率会低一些但整体不影响正确性。k为负数时先把k用Math.abs((long) k)转成正数即可因为被整除的判定在正负号上是完全等价的一个数能被 -6 整除当且仅当它能被 6 整除。6.4 追问四恰好长度为n的变体如果题目改成“恰好长度为 n”就不能再用“最早索引”的思路了。因为同余的两个前缀索引差可能大于n比如 4 和 2 差 2但你可能需要差等于 2而最早索引产生的差是 6。更直接的方法是定长窗口对每个j直接检查(preSum[j] - preSum[j-n]) % k 0。前缀和数组一次遍历搞定O(n) 时间思路反而比改 Map 逻辑更自然。这道题的价值就在这里面试官通过“至少 n”和“恰好 n”两个版本的对比能清晰看出你对前缀和的理解深度而不是只背了一个 HashMap 模板。6.5 为什么滑动窗口在这个题上不灵不少人会问能不能用滑动窗口答案是不能因为“和能被 k 整除”这个条件不满足单调性。滑动窗口的伸缩需要依赖单调性质窗口变长某种度量一定变大或者一定变小。但“和除以 k 的余数”在窗口变化时没有任何单调规律你无法判断该扩大窗口还是缩小窗口。所以这类题的正解就是前缀和 同余定理而不是双指针。能在面试时把这一点讲清楚比闷头写出代码更能体现算法功底。最后说一个我自己的调试习惯写完checkSubarraySum之后不要急着提交先本地跑几个边界用例——空数组、单元素、n1、n超出数组长度、k0、包含负数的数组。特别是把 HashMap 在每次迭代后的内容打印出来看一遍你会发现 90% 的疑难 bug 都出在“余数相同但长度不够”这条路径上。一旦想明白“必须保留最早索引”这个点这道题就没有任何玄学了。