LeetCode 1200这道题在刷题圈子里经常被当作“热身题”推荐。题目标签只有简单两个字但我在实际刷题和带人复盘的过程中发现越是这种看起来人畜无害的题越能暴露出编码习惯和边界意识上的问题。这篇文章不打算只是贴一份能通过的代码而是从题目本身出发把为什么排序、为什么相邻比较、为什么能一次遍历这些关键点全部拆开讲清楚顺便把多语言实现、复杂度分析、测试用例和踩坑记录都整理出来希望能给正在刷题的读者一份能直接参考的完整笔记。1. 题目拆解与解题思路1.1 题目到底在问什么原题描述其实很简短给你一个整数数组arr其中每个元素都互不相同请你找出所有具有最小绝对差的元素对并按照升序返回。这里有几个信息需要先拆开看。第一数组元素互不相同这意味着差值为0的情况不会出现最小绝对差一定是一个正数。第二“所有”这个词很关键说明满足最小绝对差的对子可能不止一对比如arr [4, 2, 1, 3]排完序是[1, 2, 3, 4]相邻差都是1那么答案就是[[1, 2], [2, 3], [3, 4]]三对。第三返回的元素对本身要按升序排列实际上是两重排序要求一对内部小的在前所有对子之间按第一个元素排序。从暴力解的角度想任意两两组合求绝对差复杂度是 O(n^2)数组长度最多到 10^5最坏情况 10^10 次运算这在算法题里是肯定过不了的。所以这个题的第一层考察就是能不能识别出需要更优的解法而不是直接两层循环。1.2 为什么排序是这个题的突破口把数组排成有序序列之后整个问题的结构就清晰了。举个例子arr [3, 8, 1, 5]原始顺序杂乱无章两两比较需要算 6 次差值。排序后变成[1, 3, 5, 8]这时候观察一下任意两个不相邻的元素比如1和8它们中间隔着3和5而1到3的距离是 21到5的距离是 4都比1到8的距离 7 要小。这个直觉其实可以上升成一条关键结论有序数组中最小绝对差一定出现在相邻元素之间。为了让我自己放心我用反证法验证过这个结论——假设存在一对不相邻的元素a[i]和a[j]其中j i 1构成了最小绝对差那么它们中间至少有一个元素a[k]。由于数组有序a[i]到a[k]的距离或者a[k]到a[j]的距离必然有一个不超过a[i]到a[j]的距离。换句话说如果非相邻元素构成了最小差那相邻元素中一定存在一个同样小或更小的差矛盾。所以结论成立。这个结论的意义是把问题的搜索空间从 O(n^2) 对组合直接压到了 O(n) 对相邻组合。排序本身的代价是 O(nlogn)考虑到题目数据规模这就是一个非常干净的解法。1.3 最小绝对差的性质与贪心直觉有了上面的结论解题路径就变成三步先排序再遍历一次找出最小绝对差的值最后再遍历一次收集所有差值等于这个值的相邻对。为什么这算是贪心因为每一步都做了局部最优选择排序让全局结构有序相邻比较保证了我们只需要考察最有可能产生最小差的位置不需要回头看已经扫描过的区域。这个思路在面试中很讨喜因为它逻辑闭环你能清晰说出为什么只看相邻元素就够了而不是靠猜。还有一个细节值得注意既然元素互不相同最小绝对差至少是 1但题目并没有把值域限制在连续整数所以不要假设答案一定有很多对可能只有一对也可能一对都没有不过只要数组长度大于等于 2必定存在至少一对。2. 三种实现方案与复杂度对比2.1 方案一排序加两次遍历逻辑最直白这个方案完全按照上面拆解的步骤来写代码。第一次遍历只干一件事找最小差值。第二次遍历再收集所有满足条件的对子。先看 Python 写法def minimumAbsDifference(arr): arr.sort() min_diff float(inf) for i in range(1, len(arr)): diff arr[i] - arr[i - 1] if diff min_diff: min_diff diff result [] for i in range(1, len(arr)): if arr[i] - arr[i - 1] min_diff: result.append([arr[i - 1], arr[i]]) return result这么写的好处是每一步只做一件事出错了容易定位。第一次循环结束后min_diff是全局最小值第二次循环只是机械地比对。这个方案的时间复杂度是 O(nlogn)排序占大头 O(n) O(n) O(nlogn)空间复杂度在不考虑排序递归栈的情况下是 O(1)。但我后来在实际跑测试时发现两个循环可以合并成一个因为排序之后当前元素和上一个元素的差值只会和当前的全局最小值比较不需要先完整知道最小值再回来看。这就是方案二。2.2 方案二一次遍历动态更新结果集方案二在遍历的同时维护两个状态当前遇到的最小差值min_diff以及当前所有差值等于min_diff的对子集合result。每遇到一对新的相邻对分三种情况处理差值小于min_diff说明之前的答案全部作废重置result为只包含当前这对并更新min_diff。差值等于min_diff把当前这对追加进result。差值大于min_diff什么都不用做。代码实现如下def minimumAbsDifference(arr): arr.sort() min_diff float(inf) result [] for i in range(1, len(arr)): diff arr[i] - arr[i - 1] if diff min_diff: min_diff diff result [[arr[i - 1], arr[i]]] elif diff min_diff: result.append([arr[i - 1], arr[i]]) return result这个写法的关键是重置逻辑遇到更小差值时之前收集的所有对子都要清空。我第一次写的时候忘了重置结果返回了一大堆不是最小差值的对子调试了半天才反应过来。这种动态维护最优解集的思路在算法题里非常常见比如求数组中出现频率最高的元素、求滑动窗口最大值本质都是维护“当前最优”的集合。2.3 方案三计数排序优化与适用范围再往下想一层排序真的是必须的吗如果数组的值域范围很小可以用计数排序把时间复杂度从 O(nlogn) 降到 O(n range)。具体做法是找出数组的最小值和最大值开一个长度为max - min 1的布尔数组把出现过元素的位置标记为 1然后按位置顺序扫描得到的就是有序数组。def minimumAbsDifference_counting(arr): min_val min(arr) max_val max(arr) offset -min_val bucket [0] * (max_val - min_val 1) for num in arr: bucket[num offset] 1 sorted_arr [] for idx, val in enumerate(bucket): if val: sorted_arr.append(idx - offset) min_diff float(inf) result [] for i in range(1, len(sorted_arr)): diff sorted_arr[i] - sorted_arr[i - 1] if diff min_diff: min_diff diff result [[sorted_arr[i - 1], sorted_arr[i]]] elif diff min_diff: result.append([sorted_arr[i - 1], sorted_arr[i]]) return result这个思路在数据范围可控的时候赛过直接排序但 LeetCode 原题的数据范围是[-10^6, 10^6]最坏情况下要开一个 200 万长度的桶虽然空间上勉强能接受但如果范围再大一两个数量级这个方法就崩了。所以我的建议是当作巧妙思路了解即可面试时如果面试官追问“还能不能更快”可以把这个方案拿出来展示你对空间换时间的理解但默认解法仍然用排序。2.4 三种方案的关键差异对比几种方案的核心差异可以放在一起看方案时间复杂度空间复杂度代码量适用场景排序 两次遍历O(nlogn)O(1)最少通用默认推荐排序 一次遍历O(nlogn)O(1)结果集除外中等通用面试标准写法计数排序优化O(n range)O(range)最多值域小、数据量大的特定场景从工程角度来说方案二和方案一的时间复杂度相同但方案二的代码在一次遍历中同时解决了两个问题逻辑也更紧凑。我自己的偏好是方案二因为重置结果集这段逻辑在面试时能体现出你考虑到了“答案集合可能变化”这个边界情况。3. 实操代码与踩坑记录3.1 Java 和 Go 的实现参考LeetCode 刷题最常见的工作语言还是 Java其次是 Go。这里给出两个版本的完整实现方便不同技术栈的读者直接对照。Java 版本public ListListInteger minimumAbsDifference(int[] arr) { Arrays.sort(arr); int minDiff Integer.MAX_VALUE; ListListInteger result new ArrayList(); for (int i 1; i arr.length; i) { int diff arr[i] - arr[i - 1]; if (diff minDiff) { minDiff diff; result.clear(); result.add(Arrays.asList(arr[i - 1], arr[i])); } else if (diff minDiff) { result.add(Arrays.asList(arr[i - 1], arr[i])); } } return result; }Go 版本func minimumAbsDifference(arr []int) [][]int { sort.Ints(arr) minDiff : math.MaxInt32 result : make([][]int, 0) for i : 1; i len(arr); i { diff : arr[i] - arr[i-1] if diff minDiff { minDiff diff result [][]int{{arr[i-1], arr[i]}} } else if diff minDiff { result append(result, []int{arr[i-1], arr[i]}) } } return result }Java 里我用了result.clear()再重新添加而不是直接重新new ArrayList()因为这样能复用已分配的内存。Go 里重新赋值一个二维切片反而更自然这也体现了不同语言在内存管理习惯上的差异。3.2 边界条件与测试用例清单这道题虽然简单但边界条件一点不少。我整理了一份测试用例清单建议提交之前先在心里过一遍数组长度为 2[1, 100]只有一对差值 99。有序数组[1, 2, 3, 4]所有相邻差都是 1结果有 3 对。重复元素[5, 1, 3, 1]注意题目说元素互不相同但没有说不能有重复输入如果遇到了重复元素差值 0 会成为最小绝对差要让代码自然处理这种情况实际上重复时的排序和相邻比较依然成立不含这个条件的原题测试里一般不会出现重复值但防御性编码没有坏处。负数元素[-3, -1, 2, 5]排完序后[-3, -1, 2, 5]相邻差分别是 2、3、3最小绝对差是 2。大跨度数据[1, 100000, 100001]排完序相邻差是 99999 和 1只在后一对产生结果。空数组和单元素数组虽然原题约束数组长度至少为 1 且需要返回至少一对但很多实际业务中的封装调用可能传入空数组建议加一层保护。我自己踩过的坑主要是第三个一开始我没有意识到原题可能没有重复元素但后来在牛客网改编题里看到了带重复输入的版本才发现同样的思路完全能处理只是min_diff初始化的地方要小心不能把它初始化成 0 当成最小值否则差值永远不小于min_diff结果集永远收集不到东西。3.3 几个容易写错的细节第一个坑是min_diff的初始值。有人习惯初始化成 0然后用if (diff minDiff)判断这样会导致所有差值都不小于 0第一次遇到任何差值都无法触发更新。正确做法是初始化成一个足够大的数比如float(inf)或者Integer.MAX_VALUE。第二个坑是重置逻辑的位置。如果在判断diff min_diff之前没有先判断diff min_diff那就会出现在更新min_diff后旧结果集没有被清空的问题。反过来如果先判断相等再判断小于遇到更小差值时旧结果集又被保留逻辑就乱了。这个顺序必须严格先小于后相等。第三个坑是排序后对子顺序的保证。因为数组已经排过序遍历时arr[i - 1]一定不大于arr[i]每对内部自然满足升序而遍历顺序是按第一个元素递增的所以整个结果集天然有序。如果你用了类似于“先存集合再手动排序”的写法反而是多余的还容易引入错误。4. 从一道简单题看刷题方法论4.1 排序加相邻比较一类题目的通用套路LeetCode 1200 只是“排序后相邻元素比较”这一大类的缩影。同样思路的题目还有很多比如求数组中两数之差的绝对值的最大值排序后直接看首尾元素再比如给定一个无序数组求相邻元素的最大差值LeetCode 164 最大间距排序后在原数组上找最大缺口还有一类是合并区间、求重叠区间的问题也是先排序再从头扫描相邻关系。所以我在刷题时有个习惯每做完一道题先不看题解区而是自己把解题思路抽象成一句话。这道题抽象出来就是“排序然后相邻比较”。下次再遇到类似的题我先判断能不能用这句话去套。如果套不进去再考虑其他数据结构和算法。这个方法能在短时间内把一道题的经验迁移到多道题上。4.2 与热门 100 题和简单题的关系LeetCode 热门 100 题里其实有不少排序相关的题目但很多刷题的人一上来就啃中等难度的题反而忽略了 1200 这种基础题。我的体会是简单题的价值不在于难倒你而在于帮你校准基本功。比如这道题里的排序复杂度分析、一次遍历维护最优解集、边界测试都是后面做中等题、难题时的地基。举个例子LeetCode 15 三数之和是一道典型的中等题核心思路之一就是先排序然后用双指针扫描避免三层暴力循环。如果你没想通过 1200 这种题建立“排序后相邻信息有特殊价值”的直觉做三数之和时就不容易想到为什么排序是第一件事。难度不是断层式上升的中间需要 1200 这种题来搭桥。4.3 周赛中的“秒杀”策略LeetCode 周赛的题目分四个难度第一题通常是简单题很多时候比 1200 还简单。但周赛里有个隐性要求是“快”你要在几分钟内读懂题意、写出代码并一次性通过。这时候 1200 的训练价值就体现出来了遍历逻辑熟不熟、边界条件想不想得全、标准库排序函数有没有记住都会直接影响你的 AC 时间。我参加周赛时的策略是第一题不追求最优解追求最不容易写错的解法。比如 1200 这种题方案二虽然很简洁但如果你对重置逻辑有一丝不确定果断用方案一两次遍历多花的 O(n) 时间在数据规模 10^5 以下几乎是零感知。稳永远比快更容易拿分。4.4 从复杂度分析到工程权衡如果把这个题放到真实工程场景里排序消耗的 O(nlogn) 时间很多时候根本不是瓶颈内存和代码可读性才是。比如处理一份日志数据、用户行为埋点数据数据量到了几十万条sort依然很快但如果你为了省一次遍历写出一个难以维护的循环那才是真正的灾难。计数排序的思路虽然在特定场景下能到 O(n)但它的空间占用取决于数值范围如果数组里有一个极端大的数整体空间立刻失控。这种“理论更优实际不可用”的情况在工作里太常见了。所以我个人的原则是写业务代码时优先考虑稳定性写算法题时优先考虑正确性只有在明确知道数据分布的情况下才做激进优化。LeetCode 1200 恰好是练习这个判断力的好样本。4.5 延伸练习题目推荐如果你想围绕这道题再做几道相关的题目巩固思路我建议按照下面的顺序来练习LeetCode 164 最大间距排序后找相邻元素最大差值和 1200 是镜像关系。LeetCode 219 存在重复元素 II哈希表加滑动窗口换了一种容器来比较相邻。LeetCode 15 三数之和排序加双指针是排序思路在中等问题上的典型应用。LeetCode 88 合并两个有序数组从有序性出发做归并理解排序数据的另一种利用方式。LeetCode 1365 有多少小于当前数字的数字排序加二分换一种视角看相邻关系。这几道题从易到难但核心都在处理“元素之间的相对关系”和 1200 的排序思路一脉相承。刷完这个系列你会发现面对排序相关的题目时思路会清晰很多。5. 个人实操中的一点补充最后聊一个我在实际刷题中反复验证过的细节这道题的结果集到底需不需要排序很多初学者会额外写一个排序函数对结果做处理但其实完全没必要。只要原始数组排过序遍历的连续性就保证了结果集的顺序正确性。反过来如果原始数组没有排序直接找最小绝对差对子那得到的对子之间是乱序的这时候才需要额外排序但那已经是错误解法基础上的修补了。另一个值得养成的习惯是每次提交前先手动跑一遍题目给的示例再跑一遍我自己构造的边界用例。1200 这道题的官方样例有两个一个是[4, 2, 1, 3]返回三对一个是[1, 3, 6, 10, 15]返回一对。但这两个样例都没覆盖到负数和大跨度数据我自己测的时候加上负数用例第一次就暴露了min_diff初始值的问题。刷题时见过的失败越多面试时能避开的坑就越多。