第495场周赛，Q1和Q2我加起来打了不到十五分钟。不是因为我手速多快，而是这两道题几乎是“模板级”的考法：一道用哈希做数学配对，一道用贪心做区间选择。这种题在周赛前两题里出现频率极高，真正决定你能不能拿分的，往往不是算法本身，而是边界条件有没有想全。这篇复盘适合刚打周赛、或者一直卡在Q2过不去的朋友。我会把这两题的完整思路、代码、以及赛后整理出来的边界坑都写清楚，顺便聊聊怎么把这种“套路题”变成稳定送分题。
1. Q1复盘：余数哈希，把“能被k整除的和对”压成O(n)
1.1 题面还原与第一反应
先还原一下这场的Q1。题面大致是：给定一个整数数组nums和一个整数k，统计所有满足i < j且(nums[i] + nums[j])能被k整除的下标对数量。
第一反应基本走两条路：要么双重循环直接枚举所有下标对，O(n^2)，代码最简单，但 n 稍微大一点就会超时；要么先想“整除”这个条件能不能改写成更好查的形式，这就引出了余数哈希。
我打这场比赛时，看到nums.length直接到10^5级别，立刻放弃暴力。周赛Q1虽然简单，但不等于无脑暴力，它考的就是你能不能把数学条件转成哈希查询。如果第一反应是“这不就是两重循环”，那大概率会在大数据量上吃一个 TLE。
1.2 核心思路：为什么只看余数就够了
要判断(a + b) % k == 0，不需要真的把a + b算出来。模运算有一个很直观的性质：(a + b) % k == (a % k + b % k) % k。所以两个数的和的整除性，只取决于它们各自对k取模后的余数。
进一步说，如果a的余数是r，那么b的余数必须是(k - r) % k，才能让两个余数相加后被k整除。注意这里我用的是(k - r) % k而不是k - r，因为当r == 0的时候，需要的余数也是0，而k - 0会得到k，显然不对。用(k - r) % k可以统一处理余数为0和余数非0两种情况。
剩下的事情就很简单了：从左到右遍历数组，对于当前元素x，先查一下“能跟它配对的余数”之前出现过多少次，把次数累加到答案；然后把当前余数的计数加一。先查再更新，是为了保证只统计i < j的对，不会把自己跟自己配对。
1.3 完整代码与执行示例
from typing import List from collections import defaultdict class Solution: def countPairs(self, nums: List[int], k: int) -> int: cnt = defaultdict(int) ans = 0 for x in nums: r = x % k need = (k - r) % k ans += cnt.get(need, 0) cnt[r] += 1 return ans跑一个例子验证一下。假设nums = [1, 2, 3, 4, 5]，k = 3，模 3 后的余数依次是[1, 2, 0, 1, 2]。遍历到2时，它的余数是2，需要的余数是1，之前1出现过一次，所以找到配对(1, 2)；遍历到最后一个5时，余数是2，需要的余数是1，前面1出现过两次，所以找到配对(1, 5)和(4, 5)。最终答案应该是 4 对：(1,2), (1,5), (2,4), (4,5)，和代码运行结果一致。
时间复杂度 O(n)，空间复杂度 O(k) 中不同余数的数量。如果k很大，比如10^9，也只需要哈希表里实际出现过的余数，不用担心开数组空间爆炸。
1.4 几个容易翻车的边界条件
这种题翻车点非常固定。
第一，k == 1的情况。所有数对k=1取余都等于 0，所以任意两个数相加都能被 1 整除，答案应该是n * (n - 1) / 2。代码里的(k - r) % k在这种情况下得到(1 - 0) % 1 = 0，逻辑完全正确，不需要特判。但如果你写成k - r，这里就直接炸了。
第二，负数取模。Python 的%会返回非负余数，比如-7 % 3在 Python 里是 2，而不是 -1，所以 Python 代码不需要额外处理。但在 C++ 和 Java 里，-7 % 3的结果是 -1，如果你直接拿这个结果去查哈希表，所有负数元素都会算错。C++ 的正确写法是(x % k + k) % k。
第三，答案可能超过 int 范围。n 最大10^5时，答案最大接近5 * 10^9，所以 C++ 里要开long long。Python 无所谓，但用 C++ 刷题的人很容易在这上面白给一次 WA。
2. Q2复盘：区间贪心，为什么“最早结束”总是赢
2.1 题意与暴力思路
Q2是一道区间调度题。题面大致是：给你一个二维整数数组intervals，其中每个元素是[start, end]，表示一个左闭右闭的区间。如果两个区间在数轴上有公共点，包括端点重合，就算重叠。问最少删除多少个区间，能让剩下的区间两两都不重叠。
这类题我在周赛里见过太多次。暴力做法很好想：枚举删掉哪些区间，然后检查剩余区间是否都不重叠，复杂度直接爆表。稍微聪明一点会想到动态规划：按左端点排序后，定义dp[i]表示前 i 个区间中最多能保留多少个不重叠区间，转移的时候往前找最后一个右端点小于当前左端点的区间，时间复杂度 O(n^2)。但这个数据范围是10^5，O(n^2) 必然超时。
打这场比赛的时候，我看完题大概十秒钟就在草稿纸上写了两个字：贪心。因为“删掉最少的区间”和“保留最多的区间”是等价的，而“最多不重叠区间数”正是经典的区间调度问题，贪心就是标准解法。
2.2 贪心策略与正确性直觉
贪心策略一句话：每次都选当前右端点最小的区间保留，然后跳过所有跟它重叠的区间，继续选下一个不重叠的、右端点最小的区间。
为什么按右端点排序？因为一个区间结束得越早，它给后面的区间留下的空间就越大。保留一个右端点大的区间，很可能会挡掉后面一连串本来都可以保留的区间。
举个反例你就明白了。假设区间是[[1, 5], [2, 3], [4, 6]]。如果按左端点排序，先看到[1, 5]，为了保留它，后面两个区间都没法保留了，只能保留 1 个区间；但如果按右端点排序，先选[2, 3]，然后[4, 6]跟它不重叠，可以继续选，最终保留 2 个区间。这就是右端点排序的价值。
所以我的做法是：把所有区间按右端点从小到大排序，然后从头扫一遍，维护“当前最后一个被保留区间的右端点”last_end。如果当前区间的左端点小于等于last_end，说明它和已保留的最后一个区间重叠，这个区间必须删掉；否则就保留它，并更新last_end为当前区间的右端点。
2.3 完整代码：两种排序写法
按右端点排序的写法最直观：
from typing import List class Solution: def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: if not intervals: return 0 intervals.sort(key=lambda x: x[1]) ans = 0 last_end = float('-inf') for l, r in intervals: if l <= last_end: ans += 1 else: last_end = r return ans还可以用另一种写法：按左端点排序，遇到重叠时删除右端点更大的那个区间，也就是动态更新当前保留区间的右端点为较小值。这个思路同样正确，代码如下：
from typing import List class Solution: def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: if not intervals: return 0 intervals.sort() ans = 0 last_end = intervals[0][1] for i in range(1, len(intervals)): l, r = intervals[i] if l <= last_end: ans += 1 last_end = min(last_end, r) else: last_end = r return ans两种写法的核心思想一致：让当前保留区间的右端点尽量小，给后面留空间。比赛时我更推荐第一种，因为它只需要 sort 一次，扫描逻辑也更简单，不容易写错。
拿一个典型例子走一遍：intervals = [[1,2],[2,3],[3,4],[1,3]]。按右端点排序后变成[[1,2], [2,3], [1,3], [3,4]]（同一右端点顺序无所谓）。先保留[1,2]，last_end=2；[2,3]的左端点 2 小于等于 2，删掉；[1,3]的左端点 1 小于等于 2，删掉；[3,4]的左端点 3 大于 2，保留。最终答案 2，删除的是[2,3]和[1,3]，剩下的[1,2]和[3,4]恰好不重叠。
2.4 闭区间和开区间的魔鬼差异
这个点是我最想提醒的。同样的题面，如果把区间从“左闭右闭”改成“左闭右开”，重叠判定条件会从l <= last_end变成l < last_end。区别在哪？
左闭右闭区间[1,2]和[2,3]在数轴上有一个公共点 2，所以它们算重叠；左闭右开区间[1,2)和[2,3)没有公共点，因为第一个区间的右端点 2 不包含在区间里，第二个区间的左端点 2 包含，但它们刚好擦边，不算重叠。
我见过很多人把模板背得滚瓜烂熟，一看区间的题就写if l < last_end，结果遇到左闭右闭就 WA。这场Q2明确写了左闭右闭，所以一定要用<=。以后读题时，看到区间端点带不带中括号，必须先确认清楚，再决定用哪个不等号。
| 区间类型 | 重叠条件 | 示例 |
|---|---|---|
左闭右闭[l, r] | l <= last_end | [1,2]和[2,3]重叠 |
左闭右开[l, r) | l < last_end | [1,2)和[2,3)不重叠 |
很多题解默认用开区间，遇到闭区间题时顺手抄了<，这就是那种“看起来逻辑没问题但就是过不去”的典型原因。
3. 从这场出发，拆一下周赛前两题的常见套路
3.1 Q1考的是“数学性质+哈希”
周赛Q1的定位是让大多数人能做出来，但又不至于太无脑。最常见的出题模式就是：题目给一个看似需要枚举的条件，实际上通过一个数学性质把它转成哈希查询。
比如“和能被k整除”看余数，“差等于k”看频次，“两数乘积是完全平方数”看质因数分解后的奇偶性，本质上都是同一类思路——把每个元素映射成一个“可比较的键”，然后用哈希表统计键的出现次数。
我发现很多朋友打Q1时容易陷入“模拟题面”的思维：题面说枚举就枚举，说遍历就遍历。更好的习惯是，在看到数据范围后先问自己一句：有没有办法只遍历一次？如果这个条件有“配对”的味道，那大概率就是哈希。
3.2 Q2考的是“排序+贪心”
周赛Q2最常考的算法基本就是贪心，而且贪心之前通常要排序。因为排序可以把复杂的关系变成一种确定的顺序，让贪心选择变得可证明。区间类、任务调度类、最少操作类，都是这个套路。
判断一道题能不能用贪心，核心看一步：当前局部的最优选择，是否一定不会影响后续选择。区间调度就是这样，右端点最小的区间选了不会吃亏，因为它结束最早。反过来，如果每一步的局部最优可能影响全局，那贪心就要谨慎了，这时候往往得想动态规划。
3.3 时间分配和做题顺序的小建议
我打周赛有一个习惯：前两题给自己卡一个总时间线。读题 2 分钟内完成，如果 Q1 超过 10 分钟还没思路，先看看是不是理解错了题面；Q2 超过 20 分钟没思路，果断先跳过做 Q3，回头再补。因为周赛排名看的是总得分和时间，死磕一道题是最亏的。
这场比赛我实际执行的节奏是：Q1读题30秒，写代码2分钟，跑用例1分钟；Q2读题1分钟，排序贪心4分钟，处理边界2分钟。总共不超过15分钟。这不是因为我反应快，而是这些套路见得太多了。
4. 本场碰到的边界坑，赛后统一整理
4.1 C++/Java里的负数取模
Q1对大部分Python玩家来说没什么坑，但我用C++打周赛的朋友有人直接 WA 了。原因就是 C++ 里负数取模结果还是负数，导致哈希表里存了一个错误的余数。
C++ 版核心要写成：
class Solution { public: long long countPairs(vector<int>& nums, int k) { unordered_map<int, int> cnt; long long ans = 0; for (int x : nums) { int r = (x % k + k) % k; int need = (k - r) % k; if (cnt.count(need)) { ans += cnt[need]; } cnt[r]++; } return ans; } };以后只要看到 C++ 题解里出现x % k直接套哈希，先检查负数。这个坑非常隐蔽，因为示例用例通常全是正数，本地跑得飞起，一交就错。
4.2 答案可能爆int
Q1答案的理论上限是n * (n - 1) / 2。当n = 10^5时，答案大约 50 亿，远超 32 位 int 的范围。C++ 里如果ans用int，哪怕算法全对，最终结果也会溢出变成负数。
这是周赛很常见的“隐藏陷阱”：题目本身不难，但用了大数组，就要求你考虑更大类型。建议周赛代码里所有计数型变量，只要涉及平方量级，一律用long long，省得每次都要重新估算范围。
4.3 空数组和单元素数组
Q2如果intervals为空，答案直接是 0。很多模板里用intervals[0]做初始化，结果空数组直接越界。更稳的写法是先把空数组判断掉，或者像我第一种代码那样，last_end初始化为float('-inf')，这样空数组也能走完循环返回 0。
单元素区间也是一样，不管区间本身是什么，不需要删除任何区间，答案 0。用第一种写法自然得到 0，不需要特判。
4.4 比赛里不要轻信“暴力能过”
我看到有评论说 Q2 自己写了双重循环 DP，自信能过，结果10^5数据直接 TLE。周赛是个很现实的场景：正确但复杂度不够的代码，和没写出来没有本质区别。
建议每次提交前先看数据范围：n <= 1000可以接受 O(n^2)，n <= 10^5至少要往 O(n log n) 想，n <= 10^6基本只能 O(n) 或 O(n log n) 且常数要小。周赛Q1Q2的常见数据范围基本都在10^5上下，所以“暴力一眼过”的机会越来越少。
5. 复盘后的三个变体，拿来练手刚好
5.1 把Q1改成乘积模k
Q1如果从“和能被k整除”改成“乘积能被k整除”，余数哈希就不能直接用了。因为(a % k) * (b % k) % k == 0并不简单等价于某个余数配对。比如k = 6，数2和3的余数分别是 2 和 3，2 * 3 = 6，刚好整除，但两个数都不是 6 的倍数。
更通用的做法是取每个数和k的最大公约数，然后统计gcd(x, k)的频次，再找两个数使得gcd(x, k) * gcd(y, k)是k的倍数。这个变体比原题难一个档次，适合拿来验证自己是不是真的理解透了模运算的本质。
5.2 给区间加上权重
Q2如果每个区间都有一个价值，要求删除区间的总价值最小，贪心就不再成立了。因为一个价值很大的区间可能和很多低价值区间重叠，贪心很容易把它误删。
这种加权版本的正确做法是按右端点排序后做动态规划：dp[i]表示前 i 个区间能获得的最大总价值，转移时找到最后一个和当前区间不重叠的区间。复杂度可以做到 O(n log n)，但已经不是简单贪心能解决的。
5.3 同类调度题可以串起来
区间调度是周赛的常青树，我建议把下面这几类题放一起刷一遍。
| 题目形态 | 常用方法 | 思考角度 |
|---|---|---|
| 最多不重叠区间数 | 按右端点排序贪心 | 结束得越早越优 |
| 最少删除区间使不重叠 | 总区间数减最多不重叠数 | 把删除问题转成保留问题 |
| 最少会议室数量 | 差分数组或最小堆 | 看成同一时刻并行区间数 |
| 区间合并 | 按左端点排序后扫描 | 维护当前合并范围的右端点 |
这几种题表面长得像，解法完全不同，但底层的区间思维是贯通的。把这组题刷明白，以后遇到区间类题目基本不会慌。
从第495场这场来看，Q1和Q2并不算难，但它们把周赛最核心的两个套路又考了一遍：哈希配对找数学性质，贪心排序做区间取舍。如果你也想稳定拿下前两题，可以试着把这类题各刷五道，然后在赛后第一时间复盘自己卡在哪一步，是思路没打开还是边界没想全。刷多了你会发现，所谓“手速快”，其实只是见过足够多套路之后的自然反应。
)
)
