刷题群有人甩出来一道题给你一排整数数一数里面有多少对数的值刚好相差 1。比如[1, 3, 5, 2]答案是 2 对(1,2)和(2,3)。这个题目本身不难但真正动手写的时候很多人才发现自己在审题、去重、溢出、数据规模估计这些基本功上全都没过关。尤其是有几年经验的开发者常年写业务代码一上来就是两层循环复杂度算也不算结果数据量一上来直接超时。这篇文章不只是在讲这一道题。我会从这道题展开把暴力枚举、排序、哈希表三种主流解法都走一遍顺带把边界条件、整数溢出、高精度大整数、复杂变体这些问题全部串起来。不管是准备面试、刷竞赛题还是单纯想把基础算法打牢这篇文章都能给出一份可以直接抄作业的完整参考。1. 先把问题说清楚审题往往比做题更关键1.1 这个“对”到底怎么算两种语义先定死题目写“有多少对整数它们的值正好相差 1”这里藏着第一个坑这个“对”是按数组下标算还是按数值去重后算举个例子数组[1, 1, 2, 2, 3]。如果按数组元素的下标组合来算1有两个2有两个所有相差 1 的下标组合就是 2×2 2×2 8 对。如果按“不同的整数数值”来算那就是(1,2)和(2,3)两对。绝大多数刷题场景尤其是 LeetCode 风格的问题默认按数值去重后的“值对”来统计因为题目说的是“有多少对整数”强调的是数值关系而不是下标组合。但你做题之前一定要确认好语义不然写完一版发现答案对不上还以为是自己写错了。还有一种更常见的表述是“统计数组中差为 1 的数对个数每个元素只能使用一次”这种语义下[1, 2, 2, 3]配合贪心匹配答案会是 2。不同语义对应的解法完全不一样所以我建议一上来先把这句“这个‘对’到底怎么算”问清楚这是所有讨论的地基。1.2 数据规模决定你做法的上限很多新手拿到题就直接写双重循环也不看一眼数据范围。实际刷题平台的约束通常写得很明确比如n 10^3O(n^2)随便写暴力法完全没问题。n 10^5需要O(n log n)排序或O(n)哈希。n 10^7甚至更大基本只能O(n)扫描而且要考虑内存和 IO。我见过不少人在n 10^5的场景下用了两层循环本地小数据全对提交直接超时。所以拿到题第一件事不是写代码而是看数据范围先估算一下自己能接受的复杂度上限。对于这道题O(n)到O(n log n)都是可以接受的。如果你一开始就写哈希法那连排序都不需要直接一遍过。这个选择背后的逻辑我会在下一节详细拆。2. 三种主流通解与实现细节2.1 暴力法用来验证答案的“基准测试”先看最直观的实现。两层循环枚举所有组合判断绝对差是否等于 1def count_pairs_bruteforce(nums): n len(nums) ans 0 for i in range(n): for j in range(i 1, n): if abs(nums[i] - nums[j]) 1: ans 1 return ans这段代码思路没有任何问题在n 10^3的场景下跑得飞快。但它的价值不止于此暴力法最简单、最容易验证正确性所以我在写优化版本之前总是先写一个暴力版当基准测试。后面优化版本运行结果跟它对比如果答案不一致说明优化版有 bug。这个习惯特别重要。很多人直接上手写哈希法写完拿几个小样例测一下觉得没问题就交了结果遇到重复数字的情况答案错误。有了暴力版做对照你一眼就能看出那一步错了。2.2 排序法实际刷题中性价比最高的方案排序法的思路很自然如果数组有序那么和当前元素相差 1 的数一定紧挨在它旁边。排序后只要检查相邻元素就行def count_pairs_sort(nums): nums.sort() n len(nums) ans 0 for i in range(1, n): if nums[i] - nums[i - 1] 1: ans 1 return ans等等这里有个关键陷阱如果数组里有重复元素排序后重复值会连在一起但重复值本身不会形成差 1 的数对。比如[1, 1, 2]按上面代码跑检查1和1差为 0跳过检查2和1差为 1答案加一。看起来没问题。但如果数组是[1, 2, 2, 3]呢检查2和2跳过检查3和2差为 1答案加一。这里就有问题了1和2这对被漏掉了因为1的右边紧挨着的是2但2的下标被前面那个重复的2占位了实际跑一遍你就知道排序后数组[1, 2, 2, 3]循环检查相邻元素nums[1] - nums[0] 2 - 1 1ans 1nums[2] - nums[1] 2 - 2 0跳过nums[3] - nums[2] 3 - 2 1ans 2结果还是 2 对(1,2)和(2,3)居然没丢。但这只是运气好因为我们的判断只看相邻差是否为 1。如果数组里有两个相同的 1[1, 1, 2, 3]排序后检查1 - 1 0跳过2 - 1 1ans 13 - 2 1ans 2结果(1,2)被计数了吗被计了因为那个1虽然是重复的第二个1但它在数组中确实存在数值1和2的差是 1。问题出在什么时候如果数组是[1, 2, 2, 4]照理应有(1,2)一对。跑一下2 - 1 1ans 12 - 2 0跳过4 - 2 2跳过得 1 对也没问题。我仔细想了想当差值恰好为 1 时重复值确实不太会影响相邻判断因为差 1 的两个数必然相邻出现除非中间的重复值数量特别多把这两个数分隔开。比如[1, 2, 2, 2, 3]2 - 1 1ans 12 - 2 02 - 2 03 - 2 1ans 2(2,3)被计了(1,2)也被计了结果正确。但万一重复值把相邻关系破坏了怎么办比如[1, 3, 2, 2, 2, 4]排序后[1, 2, 2, 2, 3, 4]2 - 1 1ans 12 - 2 02 - 2 03 - 2 1ans 24 - 3 1ans 3结果是 3 对实际数值对(1,2)、(2,3)、(3,4)正好 3 对。看起来差值恰好为 1 时中间无论堆多少重复值相邻差序列里总会包含一次2-1或3-2。但我不能确保任何情况下都如此稳妥的做法是先set去重再排序def count_pairs_sort(nums): nums sorted(set(nums)) ans 0 for i in range(1, len(nums)): if nums[i] - nums[i - 1] 1: ans 1 return ans这样语义最清晰先拿到所有不同数值再统计相邻差为 1 的对数。排序复杂度O(n log n)去重后元素个数最多是min(n, 不同值数量)内存可控。这个版本我强烈推荐因为它把语义和实现统一了不管你面试时怎么被追问都不慌。实际上我不确定上面那个不先去重的版本在极端情况下是否一定等价但正是这种不确定让我养成了“先 set 再排序”的习惯。做题不是猜运气确定性的解法才是好解法。2.3 哈希表法更好玩也更容易写错排序法已经很快了但还有一个更骚的操作用哈希集合存所有出现的数值然后遍历每个数检查x 1是否在集合里def count_pairs_hash(nums): s set(nums) ans 0 for x in s: if x 1 in s: ans 1 return ans这个方法的精妙之处在于把“找配对”变成了“查存在”。你不需要比较任何两个数只需要对每个数问一句x1在不在如果x和x1都在集合里那它们就是一对差 1 的数。为什么不会重复计数因为(x, x1)只会从x这边被统计一次等遍历到x1时检查的是x2是否存在跟前面那对没关系。所以答案天然不重不漏。这个解法的时间复杂度是O(n)空间也是O(n)。在数据规模很大的时候它是性能和代码简洁度上的最优解之一。三种方法对比如下方法时间复杂度空间复杂度适用场景易错点暴力法O(n^2)O(1)n 10^3 或当基准测试双层循环写错下标排序法O(n log n)O(1)或 O(n) 若用 setn 10^5 通用重复值未去重哈希法O(n)O(n)n 很大且内存够x 1溢出3. 最容易翻车的边界溢出、负数与重复值3.1 32位有符号整数的边界在哪里先说一个实战中特别常见的翻车点整数溢出。题目如果来自面试或 OJ通常会限定输入范围比如“数组元素是 32 位有符号整数”。32 位有符号整数的范围是-2^31到2^31 - 1也就是-2147483648到2147483647。这时候哈希法里写if x 1 in s就可能踩坑如果x恰好等于2147483647那么x 1在 32 位整数里会溢出成-2147483648。Python 因为是任意精度整数不会溢出但如果是 Java、C这一步直接 bug。Java 里怎么处理稳妥做法是用长整型public int countPairs(int[] nums) { SetLong set new HashSet(); for (int num : nums) { set.add((long) num); } int ans 0; for (Long x : set) { if (set.contains(x 1)) { ans; } } return ans; }把x转成long再比较就绕开了 32 位边界问题。C 则可以直接用long long。别小看这一步我见过不止一个候选人写完哈希法反问一句“如果 x 是 INT_MAX 会怎样”当场答不上来。另外负数的情况也顺便说一下。比如[-1, 0, 1, 2]差 1 的数对有(-1,0)、(0,1)、(1,2)。无论排序法还是哈希法负数天然参与比较-1 1 0逻辑没问题。唯一要注意的是abs(nums[i] - nums[j]) 1这种写法在暴力法中容易让人忽略负数其实没有影响绝对值就是为负数准备的。3.2 排序法的去重陷阱我在 2.2 节强调过“先 set 再排序”。这里再展开说一下为什么。如果不先去重排序后的数组可能长这样[1, 1, 1, 2, 3, 3]。遍历相邻元素你会发现有 3 次相邻差为 1两个1与2各相邻一次其实只有2-1那次。数值对只有(1,2)和(2,3)两对但某个错误写法可能会统计出 3 对、4 对甚至更多。再举一个更直接的例子[1, 1, 2, 2]如果按“去重后的值对”算答案应该是 1 对(1,2)。但如果不先去重只检查相邻差为 1那么排序后1 - 1 02 - 1 1ans 12 - 2 0答案确实是 1看起来没问题。但换一种写法如果用“双指针扫不同值”的方式或者用“每个数找 x1”的方式只要你没有去重答案可能变成 4。为什么因为1有两个、2有两个按下标组合来算就是 4 对。同一个题目不同解法跑出不同答案这就是语义没定死的后果。所以我反复强调进入写代码阶段之前先确认题目要的是“值对”还是“下标对”。如果是“下标对”这种情况只能用哈希计数法并且要从出现的每个位置分别配对。如果是“值对”set去重是必须的一步。3.3 求一个整数有多少位基础但实用跟这道题相关的另一个小技能是“求一个整数有多少位”。面试和刷题里经常用到比如把数组元素落到桶里、取哈希槽位、判断整数位数以决定用什么数据结构。最稳的写法是用对数import math def count_digits(n): if n 0: return 1 return math.floor(math.log10(abs(n))) 1如果怕浮点数精度问题也可以用循环除10def count_digits(n): if n 0: return 1 n abs(n) cnt 0 while n: n // 10 cnt 1 return cnt这个技能在这道题里什么时候用得到如果你要给元素分组比如按最后一位数字分类或者按位数判断可能的最大值都会用到。它不算什么高深算法但关键时刻能帮你少写很多 if。另外它和“整数排序”“逆序输出整数”这类基础题一样是我们练好基本功的一部分别嫌小。4. 经典题不是终点几个紧密相关的变体扩展4.1 01序列与整数k的限制间隔问题热搜词里出现了一个很有意思的变体“给你一个 01 序列以及一个整数 k如果所有 1 都至少间隔 k 个元素”。这其实是一个和“数对差 1”同源的统计问题只是把“数值差”换成了“位置间隔约束”。给定一个只含 0 和 1 的序列比如0100101再给一个整数k问是否所有1之间都至少间隔k个元素也就是相邻两个 1 的下标差大于等于k 1。这个问题的解法非常直接def check_gap(s, k): last_one -1 for i, ch in enumerate(s): if ch 1: if last_one ! -1 and i - last_one k 1: return False last_one i return True核心逻辑是记录上一个1的位置遇到新的1就计算下标差。如果下标差小于等于k说明不满足“至少间隔 k 个元素”的要求。注意这里的边界如果k 1要求两个1之间至少有一个0那么下标差至少是 2如果k 0则相邻1都不允许下标差至少是 1。跟“数对差 1”那题对比你会发现它们的共同点是把问题转化为相邻关系或存在性查询。数对差 1 是问值域上的邻居是否存在01 序列是问位置序列上相邻1的距离是否达标。会了前者后者基本上就是换层皮。4.2 当整数大到需要高精度Python、Java、Julia 实测“有多少对整数差 1”这个题本身不太会出现超大整数但一旦数据范围变成高精度场景比如让你从超大整数集合里找差 1 的数对事情就有意思了。先说 Python它的整数是任意精度的10**100 1随便算完全不担心溢出。所以上面哈希法在 Python 里天然免疫 32 位溢出问题。这也是为什么很多人用 Python 刷题写起来确实省心。Java 则必须用BigIntegerimport java.math.BigInteger; import java.util.HashSet; import java.util.Set; public int countPairsBig(SetBigInteger nums) { SetBigInteger set nums; int ans 0; for (BigInteger x : set) { if (set.contains(x.add(BigInteger.ONE))) { ans; } } return ans; }这里x.add(BigInteger.ONE)就是x 1但每一步都是对象运算性能和内存都比原生 int 差很多。所以高精度场景下能用原生类型就不要上 BigInteger这属于性能常识。Julia 在这方面做得比较巧妙。它的Int默认是机器整数但如果你在计算中溢出可以使用BigInt或直接让数值类型自动提升。Julia 的BigInt用起来非常顺手x big(10)^100 1 y x 1 println(y - x) # 1我在实测里发现 Julia 的任意精度整数速度比 Python 快不少和 Java BigInteger 接近但语法上更接近数学表达。如果你是那种对性能敏感又想用高精度的人Julia 是个很舒服的选择。这里也顺带提一句“Julia 高精度浮点数和整数”这个热搜词Julia 中BigFloat和BigInt是独立类型互相转换要显式调用比如BigFloat(1//3)和big(1)//big(3)的行为完全不同。写算法时一定要搞清楚自己用的是哪种避免出现“整数除法把余数丢掉”这种经典错误。4.3 大整数加法并行与排序优化的进阶思路再往深处走如果数据量特别大大到单机内存都装不下就要考虑并行和分治了。热搜词里的“大整数加法 并行”和“整数排序”其实就是这类进阶思路的关键词。大整数加法的并行思路很直白把大整数按位切分成多段每一段独立相加然后再处理进位。比如一个 1 万位的整数加法可以切成 4 段每段 2500 位四个线程同时算最后从低位到高位统一进位。回到“找差 1 的数对”这个问题上如果数据量大到需要并行最简单的做法是把排序分摊到多线程把数组切分成若干块每块独立排序。多路归并得到一个全局有序序列。线性扫描一次统计答案。这就是典型的“并行排序 串行扫描”模式。它之所以高效是因为排序是整个算法中唯一需要耗费大量时间的地方而扫描是 O(n) 的扛得住单线程。如果不想排序也可以用分布式哈希表但工程复杂度会高出很多。对大部分场景来说并行排序反而最实用。如果是用二分分治的思路来做这道题也可以这样把数组分成两半分别统计内部对数再统计跨过中点的数对。跨中点的那部分可以先把两边排序然后用双指针统计。这本质上就是归并排序的副产品复杂度依旧是 O(n log n)。这种扩展我更建议你了解一下因为面试官很爱从简单题往下追问看你有没有能力把它改成归并排序的框架。4.4 语言细节差异Java 逆序输出那道题踩过的坑有热词提到“Java 逆序输出整数”正好可以顺便聊聊不同语言处理整数时的差异因为这跟我们前面讨论的溢出问题高度相关。经典的 Java 逆序输出题是给一个 32 位有符号整数x 123返回321如果x -123返回-321如果反转后溢出则返回 0。标准写法public int reverse(int x) { int rev 0; while (x ! 0) { int pop x % 10; x / 10; if (rev Integer.MAX_VALUE / 10 || (rev Integer.MAX_VALUE / 10 pop 7)) { return 0; } if (rev Integer.MIN_VALUE / 10 || (rev Integer.MIN_VALUE / 10 pop -8)) { return 0; } rev rev * 10 pop; } return rev; }这个题和我们前面聊的“差 1 数对”有什么关系其实是同一个底层能力的两种体现对整数边界、取模、负数的处理是否够稳。写逆序输出的常见坑有三个x % 10对负数的结果是负数比如-123 % 10 -3这符合 Java 规范但很多从 Python 转过来的人会搞混Python 的-123 % 10 7。溢出判断放在rev rev * 10 pop之前否则已经溢出了再判断就晚了。边界值Integer.MAX_VALUE 2147483647、Integer.MIN_VALUE -2147483648反转后很可能会越过这个范围。这些经验不是孤立的小技巧它们跟“32 位有符号整数”这个热搜词直接相关。不管你是刷题还是做真实系统只要涉及 int 乘法、加法就要随时警觉溢出问题。“差 1 数对”这道题里的x 1溢出只是冰山一角真正的高频风险在交易金额、时间戳换算、ID 拼接这些线上场景里更多。5. 常见问题排查与工程实践补充5.1 刷题和工程中常见的坑速查表我把这道题及相关变体里最常见的坑整理成一个速查表方便你下次直接对号入座问题现象原因解决方案超时大数据量跑不动用了 O(n^2) 暴力法改为排序或哈希答案偏大把重复下标也算进去了语义未定成“值对”先 set 去重或明确下标语义答案偏小部分数对漏统计排序后未处理重复值先去重再排序遍历溢出哈希查不到 INT_MAX 的配对x 1超出 32 位范围Java 用 long 或 BigInteger负数处理错误逆序输出、差分计算不正确对%和/负数语义不熟先验证语言对负数的定义再编码大整数计算吃内存10^100 级别的统计盲目用高精度对象能用 int 不碰 BigInteger必须用时控制规模01 序列边界误判k0和k1结果一样没搞清“间隔 k 个元素”的定义明确下标差阈值是k1还是k5.2 工程中存整数怎么选类型以 MySQL 为例算法题写顺手了最后落到真实工程里整数类型的选择也是个高频话题。热搜词里有“mysql 可以存储整数数值的是”这其实就是工程中一个很实际的问题。以 MySQL 为例整数类型主要有这些类型字节数有符号范围常见用途TINYINT1-128 ~ 127状态码、开关量SMALLINT2-32768 ~ 32767小范围计数MEDIUMINT3-8388608 ~ 8388607中量级计数INT4-2147483648 ~ 2147483647常规 ID、计数BIGINT8-9223372036854775808 ~ 9223372036854775807雪花 ID、大金额回到我们的“数对差 1”问题如果你要把所有整数放进 MySQL 去重统计那字段类型就得按数据范围选普通业务量用INT如果可能超过 21 亿就上BIGINT。这里有个很多人忽略的细节MySQL 的INT在有符号时最大只能到 2147483647无符号才能到 4294967295。所以建表时除了看范围还要考虑是否有符号、是否需要无符号避免将来线上跑着跑着突然溢出报错。另外MySQL 的INT展示宽度比如INT(11)不影响存储范围它只是显示宽度。很多初学者以为INT(11)能存更大的数其实不能。这种细节在面试和实际运维中都可能被问倒。5.3 我个人在实际操作中的一些体会最后分享一点我在做这类题目和工程落地时的个人经验。我最开始也是喜欢一上来就写哈希法觉得 O(n) 很酷。后来做线上性能分析多了发现很多场景根本不需要 O(n) 的“极致优化”排序 扫描反而更容易维护。因为set虽然快但它在内存占用和哈希碰撞上的表现会受到数据分布影响最坏情况下可能退化。而排序算法是高度优化过的时间可控、行为可预测。在算法竞赛之外的真实系统里稳定比华丽更重要。还有一个小技巧遇到这种“差值固定为 1”的题目先想想它能不能用“排序后看相邻”解决。如果能通常意味着问题可以转化为相邻关系这种转化往往还能进一步迁移到其他类似问题比如“差为 k 的数对”“差为 k 的子数组”等。你掌握的是同一个思维模型而不是一道孤立的题。另外写代码前把数据范围、语义、边界条件三件事想清楚比手速快更值钱。我在带新人时就发现他们不是不会写 sort而是根本没意识到重复值会改变答案语义。每次我提醒“先 set 再 sort”他们都恍然大悟。等你踩过几次这个坑你也会明白为什么我反复强调这句话。回到标题本身题目虽然简单但它的延展性比大多数“难题”都好可深可浅从暴力到哈希到并行到高精度再到工程存储都能串起来。我写这篇东西的目的就是帮你把这条线一次走通下次不管题目怎么变形你都能一眼看穿它。