LeetCode 1200Minimum Absolute Difference是一道非常适合入门的简单题也是我每次带人刷题时都会拿出来反复讲的一个经典模型。题目本身不复杂给你一个整数数组要求找出所有差值恰好等于最小绝对差的数对。很多新手看到这道题的第一反应是两层循环暴力比较结果不仅容易超时而且代码越写越绕。实际上这道题的核心只有两步先排序然后只扫相邻元素。就这两个动作能把时间复杂度从 O(n²) 降到 O(n log n)同时保证答案不重不漏。这篇文章我会把题目背后的思维逻辑、三种可落地的写法、以及我实际刷题过程中踩过的边界条件坑一次讲清楚。1. 题目到底在考什么先读懂最小绝对差的两个关键字1.1 表面是找差值实际是考排序思维很多同学看到“最小绝对差”这五个字脑子里冒出来的第一个方案就是暴力枚举把所有数对两两相减记录最小的差再筛出所有等于这个最小值的数对。这个思路本身没错但它只看到了“找差值”没看到题目真正想考察的东西——排序思维。数组题有一个非常基础的原则当问题不要求保留原始顺序时排序往往是降低复杂度的第一把钥匙。LeetCode 1200 就是这样一道典型的题。数组里任意两个元素的绝对差数量级是 O(n²)但排序之后真正可能成为“全局最小”的候选者只剩下了相邻元素这 O(n) 个位置。这个结论看着简单但它在很多中等题和困难题里都会反复出现比如求“最小差值”“最接近的三数之和”“最大间距”等内核都是同一套逻辑。所以这道题表面上是简单模拟实际上是在帮你建立“排序预处理”的直觉。把这个直觉练成本能后面做 harder 级别题目时你会少走很多弯路。1.2 题目要求里藏着三个细节LeetCode 1200 的题目原文很短但返回值的要求里有三个容易被忽略的细节。第一个细节返回的是二维数组每一个元素是一个数对比如[[1,2],[2,3]]不是两个单独数组。第二个细节每个数对内部需要升序排列也就是小的在前、大的在后。虽然排序后的数组天然满足arr[i] arr[i1]但你如果自定义比较逻辑时写反了答案就会格式错误。第三个细节最终结果需要按数对的第一个元素升序排序如果第一个元素相同则按第二个元素升序排序。因为题目要求的是“所有”符合条件的数对不是最早找到的几个所以你必须完整地遍历一遍数组不能中途 break。这三个细节都不难但周赛中很多人栽就栽在“没看返回格式”这上面。写代码之前先把题目要求拆成三句话找什么、返回什么、顺序是什么。这比直接动手写循环重要得多。2. 为什么排序后只看相邻元素就够了2.1 暴力做法为什么不行先看暴力做法的时间复杂度。假设数组长度是 n两层循环要比较 C(n,2) 次数对也就是大约 n²/2 次。当 n 到达 10^5 这个量级时n² 就是 10^10 次操作在 LeetCode 的标准测评环境下基本是超时的。即便不超时你还要再开一个哈希表去记录哪些差值出现过内存和代码复杂度都会跟着涨。有人可能会想能不能不排序而是先遍历一次数组把元素存进哈希表然后对每个元素 x 去查 xminDiff 是否存在这个思路在某些特定题目里可行但在 1200 这道题里有一个致命问题你一开始并不知道 minDiff 是多少。要确定 minDiff你依然需要某种形式的全局比较。如果先暴力一遍找最小值再哈希一遍收集答案那时间复杂度还是 O(n²)只是把“比较的过程”换了个位置写。所以暴力不是“不行”而是“没必要”。排序 相邻扫描是这道题的最优解骨架逻辑简单代码量少还稳定。2.2 用生活里排队的例子理解相邻性为什么最小绝对差一定出现在相邻元素之间我用一个生活例子解释。假设你面前有一队人每个人的身高写在牌子上从左到右是按身高从矮到高排好的。现在你要找身高差最小的两个人。你会怎么找肯定是从前往后挨个比相邻两个人之间的身高差也就是第 1 个和第 2 个比一下第 2 个和第 3 个比一下一直比到最后。你不会去跨着人比比如拿第 1 个和第 5 个比因为中间隔着第 2、3、4 个人他们的身高一定介于第 1 个和第 5 个之间要么离第 1 个更近要么离第 5 个更近。总之跨着比出来的差值永远不可能比某个相邻差更小。这个例子说完排序后只看相邻元素的原因已经够直观了。接下来从数学上再补一刀让你彻底放心。2.3 严格证明最小绝对差一定出现在排序后的相邻位置设排序后的数组为a[0] a[1] ... a[n-1]。任取两个下标i j它们之间如果还有元素即j i1那么一定存在某个k满足i k j。我们来比较一下由于a[i] a[k] a[k1] a[j]当k取j-1或更小时对于中间的任意相邻对a[k]和a[k1]有a[k1] - a[k]是两个相邻正数的差。a[j] - a[i]是跨区间两端之差。因为a[k] a[i]且a[k1] a[j]所以a[j] - a[i] a[k1] - a[k]也就是说任意非相邻对子的差必然不少于区间内某个相邻对子的差。这就意味着全局最小绝对差一定会在至少一对相邻元素上取到。所以当你排序之后只需要扫描一遍所有a[i1] - a[i]就能拿到全局最小绝对差同时也能拿到所有等于这个最小值的数对。这个证明不需要记步骤但结论要刻在脑子里排序数组里全局最小差等同于相邻最小差。3. 从零开始写出一版能过的代码3.1 两个动作一个都不能少先 sort 再 for思路已经清楚了代码写起来就很直白。我来拆解一个最直觉的版本对数组arr原地升序排序。先遍历一次计算出所有相邻元素差值的最小值minDiff。再遍历第二次把所有差值恰好等于minDiff的相邻数对收集进结果列表。这个写法最大的优点是清晰每个步骤只做一件事。第一次遍历负责“找最小值”第二次遍历负责“收集答案”。对于刚刚接触这道题的新手我推荐先用这个版本把逻辑跑通再考虑优化成一次遍历。Python 实现如下class Solution: def minimumAbsDifference(self, arr: List[int]) - List[List[int]]: arr.sort() min_diff min(arr[i 1] - arr[i] for i in range(len(arr) - 1)) res [] for i in range(len(arr) - 1): if arr[i 1] - arr[i] min_diff: res.append([arr[i], arr[i 1]]) return res这个版本里面的min(... for i in range(...))是一个生成器表达式不会真的构建一个中间列表内存没有问题。时间复杂度为排序的 O(n log n) 加上两次线性扫描 O(n)总复杂度 O(n log n)。空间复杂度主要取决于排序算法的实现Python 的sort属于原地排序额外空间通常认为是 O(1)。3.2 二次遍历优化成一次遍历当发现更小的差值时上面的两遍扫描虽然简单但还可以压缩成一遍循环。思路是边走边记录最小差值同时维护答案列表。每发现一个新的更小差值就清空之前收集的答案重新开始记录如果遇到和当前最小差值相等的就追加进去。一次遍历版本class Solution: def minimumAbsDifference(self, arr: List[int]) - List[List[int]]: arr.sort() min_diff float(inf) res [] for i in range(len(arr) - 1): cur_diff arr[i 1] - arr[i] if cur_diff min_diff: min_diff cur_diff res [[arr[i], arr[i 1]]] elif cur_diff min_diff: res.append([arr[i], arr[i 1]]) return res这个版本我第一次写的时候差点在“发现更小差值时忘了清空 res”这个点上翻车。它虽然代码量差不多但逻辑密度更高适合已经理解两遍扫描的读者。核心区别只有一句话更新最小值的同时重置答案集合相等时才追加。两个版本跑出来的结果完全一致。非要二选一的话我建议周赛或面试时写两遍扫描版因为不容易出错工程上追求代码简洁时再用一遍扫描版。3.3 C 写法与常见实现细节如果你主要用 C 刷题核心逻辑完全一样。只是要注意std::sort是稳定排序但这里对稳定性没有要求直接用默认排序即可。C 示例class Solution { public: vectorvectorint minimumAbsDifference(vectorint arr) { sort(arr.begin(), arr.end()); int minDiff INT_MAX; vectorvectorint res; for (int i 0; i 1 arr.size(); i) { int diff arr[i 1] - arr[i]; if (diff minDiff) { minDiff diff; res.clear(); res.push_back({arr[i], arr[i 1]}); } else if (diff minDiff) { res.push_back({arr[i], arr[i 1]}); } } return res; } };这里有一个 C 新手经常踩的坑arr.size()返回的是size_t也就是无符号整数。如果你用for (int i 0; i arr.size() - 1; i)当数组长度为 0 时会因为无符号整数的“-1”变成巨大正数导致循环正常进入然后越界访问。不过 LeetCode 1200 的题目约束是数组长度至少为 2所以这个坑不会在这道题里爆出来但你在本地测试空数组时就会头大。稳妥的写法是用arr.size() - 1之前先判空或者强制转换成int。4. 这些坑我替你先踩过了4.1 重复元素是出现频率最高的边界条件数组里出现重复元素时最小绝对差会变成 0。比如arr [3, 1, 2, 3]排序后是[1, 2, 3, 3]最小差为 0正确答案是[[3, 3]]。这个 case 在示例里有时不会出现但测试集中很常见。如果你在收集答案时写成了“严格大于当前最小值才清空结果”那么相等元素会全部被吞掉。相反如果写成“小于等于”就清空那么重复元素反而会被重复追加。这两种误写我都见过。正确逻辑应该是小于当前最小值时重置等于时追加。顺序对了重复元素自然没有问题。另外要注意重复元素产生的[3, 3]是同一个下标吗不是。排序后它们来自不同下标但值相同。题目只要求元素值组成的数对不要求返回下标所以[3, 3]是合法答案。如果你在实现时用哈希表去重就很容易丢答案这也是我不推荐哈希方案的原因之一。4.2 结果排序要求容易忽略题目明确要求结果数组按数对升序排序。那么问题来了排序后的数组天然是升序的我按顺序扫描相邻元素得到的数对本身就是升序排列的吗答案是是的。因为arr[i] arr[i1]扫描过程从左到右第一次找到的数对必然是全局顺序上靠前的数对。比如数组排序后是[1, 2, 3, 4]最小差为 1扫描会依次得到[1,2]、[2,3]、[3,4]这个顺序完全符合要求。所以只要你的主数组排序用的升序答案数组不需要再额外 sort。但如果你为了奇怪的原因把数组降序排了那答案就需要翻转或者重新排序。记住升序排序解决一切顺序问题。4.3 计算差值用减法还是用 abs在已经排序的数组里由于arr[i1] arr[i]所以arr[i1] - arr[i]一定是非负数根本不需要调用abs。这也是排序带来的另一个红利差值计算变得极其干净。但有同学会问题目没让我排序如果我保留原数组用abs(arr[i] - arr[j])比较是不是也正确正确是正确但时间复杂度又回到 O(n²) 了。所以这里不是“能不能用 abs”的问题而是“要不要用排序”的问题。排序之后减法简单、逻辑直接、避免绝对值函数的额外开销一举三得。4.4 注意数组越界与循环边界我用一个两遍扫描的版本演示循环是for i in range(len(arr) - 1)这意味着访问arr[i1]时下标最大是len(arr) - 1恰好合法。如果你写成for i in range(len(arr))并且循环体内访问arr[i1]最后一步必然越界。这种错误在本地测试小样例时不容易发现因为 Python 列表越界通常会直接报IndexError你会立刻注意到。反而是 C 这种不报错的语言越界访问会给出一个随机值或者直接段错误排查起来更花时间。我的建议是写循环边界时脑子里把最后一个 i 代进去走一遍。4.5 常见错误速查表错误类型错误示范正确做法后果忘记排序直接双层循环比较原数组先sort()再线性扫描时间复杂度 O(n²) 可能超时不等值时重置if diff min_diff重置答案只有时重置会把相等差值答案丢失或重复忘记清空答案发现更小差值时直接append重置为新的列表答案混入旧的大差值数对循环越界range(len(arr))里访问 1使用range(len(arr)-1)运行时错误结果顺序错乱数组降序排序数组升序排序与题目要求顺序不符这张表是我带学弟学妹刷题时总结出来的高频错误建议写代码前对照一遍。5. 从 LeetCode 1200 延伸出去的刷题地图5.1 同类“排序相邻”模型还能解什么题LeetCode 1200 属于非常典型的一类题目排序后通过相邻元素关系来解。我举两个我刷过的高频同类题第一个是“最大间距”LeetCode 164。给定一个无序数组要求排序后相邻元素的最大差值。直观做法是排序后扫描一遍复杂度 O(n log n)能通过。进阶做法是桶排序把复杂度优化到 O(n)但思想依然是“相邻关系”。第二个是“最接近的三数之和”LeetCode 16。这题虽然是双指针但前提是先排序然后通过移动左右指针逼近目标值本质上是在利用有序数组的结构来剪枝。你如果只做 1200 这一道题可能觉得就是简单的“排序 扫描”。但如果把这三道题放在一起看会发现同一个模型在不同难度下的演化路径。1200 是入门版164 是进阶版16 是综合应用版。按这个顺序刷比单纯刷数量有效得多。另外leetcode 热门 100 题里也有好几道排序数组的题目比如合并区间、三数之和、旋转数组相关题目。它们的共同点都是一句话数组无序时先排序有序之后很多事情变得简单。5.2 为什么周赛 A 题总爱出这种题如果你参加过 LeetCode 周赛会发现很多场周赛的第一题都是这种风格题目描述不长约束范围很大暴力一定超时但思路一旦拐到“排序扫描”上几分钟就能 AC。以近期周赛题目的风格为例A 题往往不会考察复杂算法而是考察“你能否快速识别出最基础的算法模型”。1200 这种题就是教科书级的例子。它不考位运算、不考图论、不考动态规划就考一个排序意识。很多人在周赛中 A 题卡住往往不是不会写代码而是没有在第一时间想到排序。这提醒我们平时刷简单题时要刻意训练“条件反射”看到数组元素对、差值、最值这一类关键词先问自己一句排序会不会让问题变简单我之前统计过自己过去几十场周赛写的第一题至少有一半都可以用“排序线性扫描”直接解决。所以不要因为题目简单就跳过把简单题背后的模型吃透对周赛稳定性有很大帮助。5.3 与数组二分题的思路互补1200 是排序预处理模型而另一类高频题是二分查找模型比如 LeetCode 875“爱吃香蕉的狒狒”。这题表面是一个猴子吃香蕉的速度问题实际上是在一个单调区间里二分搜索最小速度。它跟 1200 有什么关系关系在于数组的“有序性”。1200 的有序是通过sort()显式构造出来的875 的有序则来自“速度越大耗时越短”这个单调关系。两者都强调同一件事很多问题在有序条件下会变得可控。如果你刷完 1200再去刷 875会更容易理解“单调性”这个概念。二分本质上是利用序列有序性来快速缩小搜索范围而排序本质上是制造有序性。它们是一体两面。我推荐的刷题路径是先把 1200 这种简单题做到闭眼能写再去做 875 这类二分题。因为二分需要的三件套——边界、单调性、循环不变量——已经比 1200 高一级了基础不牢时硬刷容易受挫。6. 我在实际刷题中的一点体会这道题我第一次做的时候其实也写过一版乱七八糟的代码先暴力找最小差值再用一个字典存所有等于该差值的数对结果不仅写得慢还差点把重复的元素搞丢。后来看题解才发现排序之后只需要三行核心逻辑。后来我刷题就养成一个习惯遇到任何“无序数组 两两关系”的题目先花十秒钟想一遍排序能不能简化问题。能简化就立刻排序不能简化再考虑哈希表、双指针或者其他数据结构。这个习惯帮我解决了很多看似复杂的题目。如果你刚刚开始刷 LeetCode我建议把 1200 作为“数组基础”这一章的第一道题来刷。先把两遍扫描版写熟再把一遍扫描版搞懂最后试着自己不借助题解从零推导出“相邻元素才有资格成为最小差值候选者”这个结论。想明白这个推导过程比 AC 这道题本身更有价值。另外一个实用的小技巧本地调试时自己构造几个特殊用例比如全相等数组、负数和正数混合、已经有序的数组、乱序大数组。把这些用例跑通比无脑提交节省很多时间。