先声明一下今天聊的MOD是模运算的mod不是游戏模组那种MOD。这篇文章要解决的是算法题里非常高频的一类问题给定数组统计满足某种整除或取模条件的子数组。这类题拿到手如果直接双重循环去枚举左右端点数据量一到10万级别就必挂。我见过太多人在这个坑里栽跟头所以把同余转化和桶优化这套组合套路彻底拆开讲一遍从数学推导到代码实现从经典题目到变种扩展一次说透。1. 同余转化把“整除判断”翻译成“余数相等”1.1 先从一个高频问题说起力扣第974题“和可被 K 整除的子数组”是我刷题这么多年遇到的最典型的同余应用。很多人第一次看到这个题目第一反应都是枚举左端点、枚举右端点、算区间和、判断能不能整除K。思路不能说错但复杂度完全失控。n是10^5时n(n1)/2个区间算一遍就是10^10级别操作稳稳超时。换个角度想判断“某个整数能不能被K整除”本质上就是判断“这个整数模K是不是余0”。那如果我们能把区间和这种动态变化的东西转换成一个容易维护的静态属性问题就好办了。前缀和就是干这个的。一旦引入前缀和整个问题就从“算一堆区间和”变成了“比较两个前缀和的关系”这一步是今天所有内容的起点。1.2 前缀和公式推导区间和怎么变成余数比较先写下基础定义。pre[i]表示数组前i个元素的和并且规定pre[0] 0表示一个元素都不取的“空前缀”。那么从下标l到下标r这个区间的和就等于pre[r 1] - pre[l]。这是前缀和的标准用法背熟就行。现在关键来了。我们要求的是区间和能被K整除也就是(pre[r 1] - pre[l]) % K 0这个式子等价于什么等价于pre[r 1]和pre[l]在模K意义下余数相同写成pre[r 1] % K pre[l] % K这步转化就是整个算法里最核心的“同余转化”。你可以用带余除法验证一下两个数之差能被K整除当且仅当这两个数除以K的余数相等。比如11和1都除以5余数分别是1和1所以11 - 1 10能被5整除。再比如7和2余数分别是2和2所以7 - 2 5也能被5整除。一旦抓住这个等价关系“统计能被K整除的子数组数量”就变成了“统计有多少对前缀和的余数相等”。问题性质完全不同了。1.3 为什么转化后复杂度能降一个量级暴力做法要枚举所有l和r组合数是n(n1)/2复杂度O(n^2)。同余转化之后我们只需要从左到右扫一遍数组每扫到一个位置问一个问题当前这个前缀和的余数之前出现过几次每出现一次就说明能和之前某个前缀配成一对产生一个合法子数组。为什么配对数量可以直接累加因为余数相同的关系是等价关系如果pre[a]余数是rpre[b]余数也是r那么pre[a]和pre[b]的差一定被K整除对应的区间一定合法。反过来如果区间合法两个端点的前缀和余数一定相同。所以一对一同余的前缀和就是一个合法子数组不多不少。这个思路的本质是把问题从“笛卡尔积式的两两比较”压缩成了“线性扫描加查表”。我打个比方班里统计生日相差能被7整除的同学对数暴力做法是两两比较365天聪明做法是按星期几分成7组只需要统计组内组合数。这个“按星期几分组”的动作就是桶优化的雏形下一章细说。2. 桶优化用计数器把两层循环压成一层2.1 桶里到底存什么同余转化做完以后我们需要一个数据结构把“余数”映射到“出现次数”。这个数据结构就是桶。桶的下标是余数桶里存的值是这个余数已经出现了几次。遍历到每个元素时把当前前缀和pre取模得到r然后做两件事第一ans加上cnt[r]第二把cnt[r]自增1。顺序绝对不能反。如果先自增再累加就会把当前前缀和自己跟自己配对的情况也算进去形成一个长度为零的“空子数组”导致答案多算。为了加深理解看一个最简单的例子。nums [5], K 5。初始化桶cnt {0: 1}。扫到5pre 5r 0ans cnt[0]也就是1然后cnt[0]变成2。最终答案是1。这里ans加上的1对应的就是子数组[5]本身。如果没有提前把余数0放进桶里答案就会算成0全错。这个初始化细节我在第5章还要重点强调它是新手最容易漏的地方。2.2 负余数陷阱统一模系取模运算有个让人头疼的细节负数怎么取余。C和Java里-2 % 5的结果是-2而Python里-2 % 5的结果是3。如果拿到一个负余数直接去访问数组下标或者作为哈希键程序会直接出问题要么越界要么统计出错。统一处理方式是用一个防御性公式r (pre % K K) % K这个式子的原理很简单pre % K先把结果限制在(-K, K)区间内加上K以后变成(0, 2K)区间内的正数再取一次模结果必然落在[0, K-1]。无论pre是正是负最终得到的r都是合法的非负余数。我用一个具体例子演示为什么要这样处理。假设K 5某个前缀和pre -2。在C里直接-2 % 5得到-2把这个-2作为桶下标访问cnt[-2]显然不对。用公式算一下(-2 % 5 5) % 5 (-2 5) % 5 3 % 5 3正确余数是3。因为-2和3在模5意义下确实同余-2 5 * (-1) 3。2.3 数组桶 vs 哈希桶怎么选实现桶有两种常见方式选择标准主要看K的大小。第一种K在10^6甚至10^5以内时直接开一个长度为K的整型数组。初始化全0。数组下标访问是O(1)常数极小而且是连续内存缓存命中率高实测性能远好于一切哈希结构。第二种K非常大比如1e9根本开不了那么大的数组就只能用哈希表只存储出现过的余数。时间上仍然是O(n)但因为哈希碰撞、扩容等原因常数比数组大不少。我个人的选型原则是竞赛或者面试环境里能开数组就开数组空间换时间非常划算。只有K确实大到没法开数组时才用哈希。原因很简单数组桶最坏情况就是k个位置的随机访问性能可预期哈希桶在最坏情况下可能因为碰撞严重而退化成O(n^2)虽然实际很少出现但没必要给自己留隐患。方案时间复杂度空间复杂度适用场景暴力双重循环O(n^2)O(1)n ≤ 1000前缀和 数组桶O(n)O(K)K ≤ 10^6性能最优前缀和 哈希桶O(n)O(n)只存出现过的余数K任意K很大时使用3. 从零实操三道经典题的思路、代码与手推3.1 题一和可被K整除的子数组力扣974题目描述很长核心就一句给一个整数数组nums和一个整数K返回数组中能被子数组和整除K的连续非空子数组的数目。标准解法就是前缀和加同余桶。Python代码非常干净def subarraysDivByK(nums, k): cnt {0: 1} pre 0 ans 0 for x in nums: pre x r pre % k # Python的%保证结果为非负 ans cnt.get(r, 0) cnt[r] cnt.get(r, 0) 1 return ansC版本需要注意负数取模的问题int subarraysDivByK(vectorint nums, int k) { unordered_mapint, int cnt; cnt[0] 1; int pre 0, ans 0; for (int x : nums) { pre x; int r (pre % k k) % k; // 统一非负余数 ans cnt[r]; cnt[r]; } return ans; }我用题目自带的示例nums [4,5,0,-2,-3,1], K 5一步一步手推一遍。这个过程非常重要建议你自己也在纸上跟着画一遍。定义桶cnt初始状态是cnt[0] 1表示空前缀pre[0] 0的余数0已经出现一次。然后逐个扫描扫描元素当前pre余数r累加前cnt[r]ans更新更新后cnt初始---0{0:1}44400{0:1, 4:1}59411{0:1, 4:2}09423{0:1, 4:3}-27203{0:1, 4:3, 2:1}-34436{0:1, 4:4, 2:1}15017{0:2, 4:4, 2:1}最终答案是7和官方示例输出一致。这张表建议多看两遍你就能直观理解“每遇到一个已经出现过的余数就多了一批新的合法配对”这个逻辑。比如扫到第三个元素0时余数4已经出现过两次所以ans从1变成3说明新增了两个合法子数组。3.2 题二和为K的子数组力扣560——同余桶的“近亲”力扣560题是“和为K的子数组”虽然名字里没有“整除”但它和974题共用同一个前缀和加桶的框架。唯一区别是974题比的是“余数相等”560题比的是“差值等于K”。推导过程是这样的要sum(l..r) K等价于pre[r 1] - pre[l] K也就是pre[l] pre[r 1] - K。所以每扫到一个位置答案要加上“之前有多少个前缀和恰好等于当前pre - K”然后把当前pre放入桶中。def subarraySum(nums, k): cnt {0: 1} pre 0 ans 0 for x in nums: pre x ans cnt.get(pre - k, 0) cnt[pre] cnt.get(pre, 0) 1 return ans注意这里桶的键不是余数而是真实的前缀和值。你能清楚区分974题和560题的差别说明你真正理解了前缀和加桶的通用框架。两题的代码结构几乎一模一样唯一的灵魂差异就是“桶里存什么、查什么”。3.3 题三最长的和能被K整除的子数组再升级一下不统计数量要长度。思路同样用同余桶但桶里不再存“出现次数”而是存“某个余数第一次出现的位置”。维护一个字典firstkey是前缀和的余数value是这个余数第一次出现的下标位置。注意这里的下标我用“已扫描元素个数”表示。扫描过程中如果当前余数已经出现过就用当前位置减去first[r]得到一个候选长度更新最大值如果没出现过就记录first[r]为当前位置。def max_len_divisible(nums, k): first {0: 0} pre 0 ans 0 for i, x in enumerate(nums, 1): pre x r pre % k if r in first: ans max(ans, i - first[r]) else: first[r] i return ans这段代码里有几个点需要解释。第一初始化first[0] 0对应空前缀的位置0。第二只有当余数第一次出现时才记录位置这样才能保证“当前位置减去首次出现位置”得到的差是“该余数类里最长的子数组”。第三题目如果要求子数组必须非空还要额外加个判断确保长度大于0。这个变种题完美诠释了桶优化的灵活性桶的结构不变桶里的“值”从计数变成了下标解决的问题就完全不同了。这也提示我们遇到新题不要僵化套模板先想清楚题目到底要什么再去决定桶里存什么。4. 同余桶思想的更多战场校验码、循环节与状态压缩4.1 校验码里的同余ISBN-10与mod 11/10很多人以为同余和桶只存在于算法竞赛中其实它在现实工程里应用特别广。最典型的就是ISBN-10书号的校验算法。ISBN-10的规则是前9位数字依次乘以10、9、8、…、2得到一个加权和sum然后计算校验位check (11 - sum % 11) % 11。如果结果等于10就用X表示。举例来说假设前9位是0-306-40615那么加权和是010 39 08 67 46 05 64 13 5*2 142142 % 11 10check (11 - 10) % 11 1所以校验位是1完整书号是0-306-40615-1。这个校验过程本质上就是“把一串数字压缩成一个模11的余数再检查余数是否符合特定值”。你看它和974题里“把前缀和压缩成模K的余数再检查余数是否相同”是同一个思维模型。理解了这个刷题时就多了一层亲切感原来我们天天用的书籍编号背后就是同余理论在支撑。4.2 循环节、环形数组与同余分组再往深走一层。只要数据存在“周期为K”的性质同余分组就是天然优化方向。我做模拟题时遇到过很多“状态每走一步对M取模”的题处理经验是余数一旦出现重复就意味着进入循环后面一大段状态序列会周而复始地重复可以直接跳过不用一步步傻算。环形数组问题也是如此。有人喜欢把数组复制一份来模拟环其实可以直接用下标对数组长度取模来完成环形定位。本质上还是在用模运算处理循环结构。同余分组的通用价值在于它把“连续数值域”比如前缀和的范围可能非常大压缩成“离散的K个类”。数据一旦被分进K个同余桶里后续的查重、计数、求最长距离、判断循环都只发生在桶内部和全局无关。这就是降维。4.3 状态压缩里的同余判断动态规划里同样大量出现同余。比如集合划分问题要求判断能否把一些数分成若干组每组和相等。如果总数对K有整除约束余数往往直接可以作为DP状态的一维。再比如某些背包优化枚举数量维度时可以按模K分成几个类每个类内部单独做单调队列优化从而把一维循环的复杂度降下来。这类题型的共同点都是表面上看不出“同余”两个字但一旦你把数据按模K分类规律就出来了。这就是为什么我一直强调同余桶不只是“一道题的解法”而是一种通用的算法直觉。当你看到整除、取模、循环、周期这几个关键词时大脑就应该自动弹出“前缀和 同余 桶”的候选方案。5. 常见问题与排查技巧实录5.1 负数取模的跨语言差异这是所有坑里出场率最高的一个。C和Java对负数取模会保留负号Python则保证结果和除数同号所以除数为正时结果非负。直接用语言默认的取模结果作为桶下标是必错写法。错误写法示范int r pre % k; // 如果pre是负数r可能是负数访问数组越界正确写法int r (pre % k k) % k;再提醒一个点如果K本身可能为负数这个防御公式也救不了你。虽然题目一般给正整数K但万一遇到先把K取绝对值再统一处理。5.2 桶初始化漏掉pre[0]第二个高频bug是忘了把pre[0] 0对应的余数0在桶里初始化为1。这个初始化代表“空前缀”的存在。没有它所有从数组开头开始且满足条件的子数组都会被漏统计。我再用一个极小例子验证。nums [5], K 5结果应该是1。如果不初始化cnt[0]桶为空扫到5时r 0ans 0答案是0直接错误。初始化cnt[0] 1后ans 1答案正确。工程上怎么避免这种错建议把“前缀和桶”的初始化写成固定两步先建桶然后显式cnt[0] 1。不管题目里数组是什么这个步骤永远不省。5.3 前缀和溢出与取模时机数组元素很大、n也很大时pre的累加值很容易超出int范围。两种处理方式一是把pre声明为long long二是只保留模K后的余数前缀。第二种有个前提题目只关心余数之间的比较关系比如974题。这里给出余数前缀的写法int r 0; for (int x : nums) { r ((r x) % k k) % k; // 用r做桶查询和更新 }因为(a b) % k (a % k b % k) % k所以这样维护出来的r和“先维护完整pre再取模”结果完全一致还省掉了long long。但560题这类需要比较pre - K精确值的题目不能这么省必须维护真实前缀和否则信息丢失答案必然错。到底用哪种就一条判断标准题目要的是余数关系还是数值关系。5.4 哈希桶的退化问题最后聊下哈希桶的性能隐患。unordered_map在平均情况下是O(1)但遇到数据构造不好的场景可能退化尤其是K在2的幂附近很多数值的低位高度重合时桶内元素容易扎堆。竞赛中如果时限卡得很紧这就是致命的。我的应对策略是三级方案第一优先数组桶K允许就开数组第二如果K很大但n不大可以把所有余数记录下来排序后统一统计避开哈希的动态扩容和碰撞问题第三实在要用哈希表就自己写一个简单可靠的哈希函数或者直接换map把时间稳定在O(n log n)。前面提到的mod 11/10校验也是一个思路校验算法往往用固定模数不依赖动态哈希所以性能和时间复杂度都可精确预估。做工程或者竞赛稳定性永远排在第一位。最后再分享一点个人体会。同余转化和桶优化这套组合最值钱的地方是一套思维习惯看到整除、取模、重复周期立刻想到前缀和、余数分类、桶内聚合。我当年第一次接触974题时也觉得巧妙但真正搞懂是在纸上把前缀和的每个余数列出来之后。那一刻我才发现所有合法子数组其实就是那些“相同余数”之间的连线。希望你也能亲手做一遍这个推演那个豁然开朗的瞬间比背任何模板都值钱。