前缀和+同余+哈希表：破解“连续子数组和可被k整除”的2024题22

1. 题面只有三行，但它如何骗过了我的第一反应

1.1 原题描述与数据范围

在整理2024年热题清单的时候，我注意到一道被很多人称为“2024年题22”的题。它出现的频率高得离谱，但绝大多数人只记得“这题很简单”，却说不出到底考了什么。题面确实不长：

给定一个整数数组 nums 和一个整数 k（k > 0），找出 nums 中长度最长的连续子数组，要求该子数组的元素之和可以被 k 整除。如果不存在这样的子数组，返回 0。

真正决定这题难度的，是隐藏在后面的约束条件：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= 10^9

看到这个数据范围，懂行的人应该立刻产生两个判断：第一，这题肯定不是让你枚举所有子数组；第二，它大概率跟前缀和或者类似“区间和快速计算”的套路有关。

1.2 “看起来简单”是这题的第一层陷阱

我说它骗人，是因为几乎所有第一次看到这道题的人，第一反应都是同一个：枚举所有子数组，算一下区间和，检查能不能整除。为什么？因为“连续子数组”这个词太顺滑了，顺着读下来，脑子里自动生成了双层循环的轮廓。

但把思路停在“两层循环”上的人，往往漏看那一行关键信息：n 最大 10 万。两层循环就是 10^10 次操作，这还只是遍历，没算区间求和的消耗。一台普通开发机，每秒大概能执行 10^8 到 10^9 次简单运算，你需要几十秒甚至几分钟才能跑完，这已经接近不可接受的等待时间。

更狠的是，如果你在内部每次都用 sum(nums[i:j]) 或者切片求和，实际复杂度会退化得更严重。这就是这类题的第一层包装：它真正想考的，并不是你能不能想到枚举，而是你能不能看穿枚举的底线在哪里。

1.3 暴力解的耗时账本：不是慢一点，是根本跑不完

为了确认“有多慢”，我在本地用 n=100000、随机整数、k 取某个随机正整数，跑了一次暴力解法。这里我用的是滑动维护的方式，内部不需要重新求和，已经是暴力枚举里比较体面的写法了：

def brute_force(nums, k): n = len(nums) best = 0 for i in range(n): s = 0 for j in range(i, n): s += nums[j] if s % k == 0: best = max(best, j - i + 1) return best

这段代码在 n=10000 时已经能明显感觉到卡顿，在 n=100000 时属于“点完运行可以去倒杯水回来还没结束”的状态。我跑了几分钟没有等到结果，最终手动终止了。

所以第一课很简单：见到子数组、子串、区间和这类词，先看数据范围。看到 10^5 还想着枚举，那就已经输掉一半了。

2. 把“整除”翻译成“同余”：前缀和思路的突破口

2.1 先补前缀和的基础定义

前缀和是一个很基础但极其常用的工具，它用一个数组 pre 记录从数组开头到某个位置的累计和。通常约定 pre[i] 表示 nums[0] 到 nums[i-1] 的和，并且 pre[0] = 0。

这样任意区间 [i, j) 的和，就可以快速算出来：

sum(i, j) = pre[j] - pre[i]

也就是说，区间求和从一个可能很长的循环，变成了两个前缀和的一次减法。很多子数组问题，第一步都应该做这个转换，2024年题22也不例外。

2.2 整除条件的等价变形

把题目条件代入：区间 [i, j) 的和能被 k 整除，等价于：

(pre[j] - pre[i]) % k == 0

这个式子又可以等价转换成：

pre[j] % k == pre[i] % k

为什么能这样换？因为 (a - b) % k == 0 的本质，就是 a 和 b 对 k 同余。这是数论里最基本的同余关系，但不少人在做算法题时不会主动往这个方向想。

这道题的核心考察点，恰恰就是这一下：从“区间和被 k 整除”翻译成“两个前缀和对 k 的余数相同”。翻译一完成，后面的代码思路就顺了。

2.3 从“检查所有区间”到“只记录最早位置”的思维跳跃

一旦条件变成“余数相同”，问题就彻底换了形态：从左到右计算每个前缀和的余数，如果某个余数在之前出现过，那么从第一次出现的位置到当前位置之间，就存在一个满足条件的子数组。

这里的关键优化点在于：题目求最长长度，所以对同一个余数，只需要保留它第一次出现的位置。后面再遇到同余数，直接用当前位置减去最早位置，就得到一个候选长度。

这个行为很像查字典：余数是单词，第一次出现的位置是单词第一次出现的页码。遇到重复单词时，不需要更新页码，只需要计算当前行号和第一次页码之间的距离。

于是整个算法只需要一次遍历，时间复杂度 O(n)，空间复杂度取决于哈希表存储的余数种类，实际是 O(n)。相比暴力解，这是一次质的飞跃。

3. 哈希表方案的三个返工坑：每个坑都让我多花了半小时

3.1 字典的键值设计：存余数还是存下标

我见过不少同学在这里把字典写反，键存下标、值存余数。这样写不是说完全不能工作，但当你真去实现“回头查余数对应的最早位置”时，就会发现键必须是余数，值才应该是下标。

正确的结构是：

# 键：前缀和 % k 的余数 # 值：该余数第一次出现时，前缀和对应的下标 first_seen = {}

这个设计成立，是因为我们最终关心的只有“位置距离”，而位置距离由 i - first_seen[remainder] 得到。如果键值放反，每次想要找回同一个余数最早出现的位置，就得遍历一次字典，复杂度又回去了。

3.2 负数取模不统一：换语言时最容易翻车

这题输入里有负数，于是牵扯到不同语言对取模结果的定义差异。

数学上，a % k 通常约定为非负余数。但 C++、Java 的 % 运算符，结果的正负会跟随被除数的正负。例如 -7 % 3，数学上应当是 2，但在 C++ 里结果是 -1。

假设你在 Python 里写完正确代码，准备平移成 C++ 或 Java，如果直接写 prefix % k，遇到负数就会出现问题。因为负数余数在同余判断时不能直接比较，-1 和 2 在数学上对 3 同余，但在代码里 -1 != 2。

解决办法是写一个统一的取模修正：

int r = prefix % k; if (r < 0) r += k;

这个坑几乎每次做负数取模相关题目都会出现，值得养成条件反射。

3.3 初始值{0：-1}的含义，以及为什么{0：0}是错的

很多初学的人在初始化时写 first_seen = {0: 0}，理由是 pre[0] = 0，余数 0 在下标 0 出现了。这个理由本身不算错，但会导致一个隐蔽问题：如果整个数组的第一个元素就能被 k 整除，比如 nums = [6]，k = 3，那么在 i=0 时，prefix = 6，remainder = 0，哈希表里已经有 0，于是 ans = 0 - 0 = 0，长度为 0，而正确答案应该是 1。

问题出在哪？出在“下标 0”这个位置被两个含义混淆了：一个含义是“前 0 个元素的前缀和”，另一个含义是“第一个元素 nums[0] 所在的位置”。这两者必须分开。

正确的初始化是 first_seen[0] = -1，表示“在数组开始之前，已经存在一个前缀和等于 0 的位置”。这样遇到 nums = [6] 时，ans = 0 - (-1) = 1，立即得到正确结果。

这个 -1 看起来像是“无中生有”的初始化，但它是整套同余逻辑成立的前提：前 0 项的前缀和是 0，它位于数组任何元素之前。

4. 手算推演与实测：这道题的确认过程

4.1 用一个示例完整跑一遍

我用一个稍微复杂一点的例子做手算推演：nums = [5, 3, 1, 2, 4]，k = 3。

这里最值得注意的，是下标 2 和下标 4 的两次余数 0 判断。它们都用到了初始化时写入的 -1，说明 -1 不只是“防呆”，它真的参与长度计算。

4.2 边界测试用例清单：把常见错误暴露出来

我在本地补了一组边界用例，专门用来验证那些容易写错的地方：

如果你用一种解法把这些用例全部跑通过，那代码基本就站得住脚了。

4.3 三种方案耗时实测对比

我在本地用 n=100000 的随机数组做了一次简单对比：

可以说，从暴力解到哈希表方案，不是“快了一点”，而是从“跑不完”变成了“几乎瞬间完成”。这种量级的差异，才是这类题设计数据范围的真实意图。

5. 从2024年题22延伸出的三个练习方向

5.1 “简单题”真正该练的是什么

这道题被很多人标记为简单，其实它考的并不是多么花哨的算法，而是基础概念的迁移能力：从暴力到前缀和，再从前缀和到同余，每一步都只需要高中数学基础，但组合起来就能难倒一大批人。

我的建议是，刷到这类题，不要只看最终代码，而是要在纸上把三个“为什么”回答完：为什么需要前缀和？为什么前缀和的比较变成了同余？为什么哈希表里存的是第一次出现位置而不是最后一次？这三个问题能回答清楚，才算真正拿下这题。

5.2 同类型问题识别清单

练完这道题之后，你会发现自己能识破一批包装不同的同类题。我把最常见的几种形态整理如下：

这些都是同一套“前缀和 + 哈希表”思想的不同外衣。

5.3 改变条件再练一遍：把原题改出三个变体

学完之后最有效的巩固方式，是动手改造原题，而不是去刷更多类似的题。

变体一：求长度最短的满足条件的子数组。思路不变，只是把哈希表里“第一次出现位置”改成“最后一次出现位置”。

变体二：把“整除 k”改成“模 k 等于 x”。代码几乎不用变，只是每次判断余数时要去找余数 (x + current_remainder) % k 的位置，初始化逻辑也多了一层。

变体三：改成计数题，问“一共有多少个连续子数组的和能被 k 整除”。这时哈希表的值不能再存下标，而要存出现次数，并且每次遇到已有余数时要把历史次数累加起来，最后注意余数 0 的初始次数。

这三个变体都自己实现一遍，你会真正掌握前缀和哈希模型，而不是只会背一道题的答案。我在实际做题中越来越体会到，很多所谓的简单题，真正的价值不是让你获得一次通过，而是逼你在某个看起来不起眼的地方，把概念彻底想明白。2024年题22对我来说就是这样一道题。