★ FEATURED ARTICLE 最近在刷算法题的时候碰到一道很有意思的数组题给定一个排好序的数组再给一个整数 k 和一个目标值 x要你找出数组里最接近 x 的那 k 个元素并且返回结果还得保持升序。听着不难但真动手写很多人会在相等距离、窗口边界、结果顺序上栽跟头。这篇文章就围绕这道经典的双指针题目把思路、证明、代码和坑一次讲清楚适合刚接触双指针的读者也适合准备面试想把这题吃透的朋友。1. 先理解题目K 个最接近的元素到底在考什么1.1 题目拆解与输出要求这道题的原始描述很短给定一个升序排列的整数数组arr以及两个整数k和x从数组中找到最靠近x两数之差最小的k个数。返回的结果必须按升序排好。但“最靠近”不是只看差的绝对值题目里有一条容易忽略的规则如果两个数到x的距离一样那么更小的那个数算作“更接近”。打个比方x 3数组里有1和5距离都是 2此时1会被优先选中因为 1 5。这个规则直接决定了我们写比较条件时等于号到底站在哪一边。输入约束一般包括1 k arr.length数组长度最大可以到 10^4 甚至 10^5 级别所以暴力计算所有元素距离再排序的做法虽然能过但不是最优解。返回值要求是原数组中的一个连续片段这点可以从“数组已排序”和“最终结果升序”推断出来但很多人一开始没意识到后面会解释为什么一定是连续的。1.2 直觉为什么结果一定是一个连续子数组先抛结论在升序数组中最接近x的k个元素必然构成原数组中的一个连续窗口。用反证法想就通了。假设选出的k个元素里有两个位置i j中间漏掉了某个元素arr[m]i m j。如果arr[m]不在候选里那么它要么在x的左侧要么在右侧。数组有序所以arr[m]到x的距离一定不会比arr[i]或arr[j]同时都更远。更直白地说你把窗口两端往中间漏掉的位置挪一下把最远的那两个端点换掉总距离只会更小或持平。反复这么替换最后一定能得到一个连续的区间。这个直觉很重要。因为一旦确定答案是连续子数组问题就从“从 n 个数里挑 k 个”简化成了“在 n 个位置里找一个长度为 k 的窗口窗口内的元素整体最接近 x”。双指针解法就是围绕这个窗口来的。1.3 三个常见切入点暴力排序、堆、双指针见到这道题不同的人会有不同第一反应。第一个是暴力法算出每个元素与x的绝对差按照“距离小优先距离相同数值小优先”排序取前 k 个最后再对结果排序。这个做法思路简单但排序的时间复杂度是 O(n log n)在数组很长时不够优雅。不过它很适合用来验证其他解法对不对我调试的时候经常拿它当“标准答案”。第二个是堆维护一个大小为 k 的最大堆堆顶是当前距离最远的元素遍历数组时如果新元素比堆顶更接近就替换掉。时间复杂度 O(n log k)空间 O(k)。能解但相比双指针还是重了。第三个就是双指针要么从整个数组的两端逐步收缩要么先二分定位再左右扩散。这个方案能把时间复杂度压到 O(n) 甚至 O(log n k)而且代码量很少。下面重点讲的就是这条路。2. 双指针解法从两端收缩窗口的思路与原理2.1 维护一个超宽窗口逐步丢掉更远的那头既然最优答案是一个长度为k的连续窗口那么最笨但最稳的做法是先拿整个数组当窗口此时窗口长度是n比k大。我们的目标就是把窗口缩到k长度每次收缩只能丢掉左端点或者右端点丢掉的标准很简单比较左端点和右端点谁离x更远丢掉更远的那个。算法骨架如下初始化left 0right arr.length - 1。只要窗口长度right - left 1 k就循环如果左端点离x的距离不大于右端点说明右边更远或一样远。按照“相等时选更小元素”的规则丢掉右端点即right--。否则左端点更远丢掉左端点即left。循环结束后返回arr[left]到arr[right]这段连续子数组。这里的关键是“相等时丢右边”。很多人写这道题时条件写反导致示例输出变成[2,3,4,5]而不是[1,2,3,4]。两者距离和都一样但题目要求“多个答案时返回更小的元素”所以必须往左靠。2.2 这个贪心策略为什么成立你可能想问每次只看两个端点丢掉一个这样贪心真的不会把正确答案丢掉吗这是双指针题里最值得讲清楚的地方。因为数组是有序的所以对于任意一个窗口[left, right]如果它的长度还大于k那么最终答案窗口必然不包含左端点或者不包含右端点至少丢掉一个。问题是先丢谁。我们可以用“排除法”来思考。假设左端点arr[left]到x的距离大于右端点arr[right]到x的距离也就是arr[left]更远。那么无论最后保留的k个元素是哪些只要窗口还包含左端点它的总距离就会大于等于另一个同样长度但向右移动一位的窗口。因为arr[left]已经是当前窗口里离x最远的那一端的元素之一丢掉它不会让答案变差。反过来如果右端点更远就丢掉右端点。如果两端距离一样选择丢掉右端点、保留左端点正好符合“更小元素优先”的规则。这个推理有一个隐含前提数组元素是升序的所以左端点永远是窗口里最小的元素右端点永远是窗口里最大的元素。越靠左未必离x越近但当我们比较两端时只要丢掉更远的一端窗口就会向更近的方向收缩。重复这个过程窗口会保持“当前长度下最优”的性质最终收缩到长度k时它就是你想要的答案。2.3 另一种双指针二分定位后左右扩散除了“从外向内收缩”还有一类双指针思路是“从中心向外扩散”。做法是先用二分查找找到x在数组中的插入位置idx也就是第一个大于等于x的位置然后让left idx - 1right idx两个指针从中间往两边走每次选距离更近的那一边加入结果选够k个为止。这个思路很直观但实现起来坑很多要考虑left或right越界、距离相等时选哪边、最终收集到的顺序是乱的需要排序或倒序插入。它适合帮助理解实际面试时我更推荐第一种“收缩窗口”的写法因为代码更短、边界更简单、逻辑也能自圆其说。不过由于这个思路也常被称为“二分 双指针”我会在后面的代码章节给出一个可用的实现。这里先记住一个重要结论无论从外向内还是从内向外本质都是利用“数组有序 答案连续”这两个性质。3. 完整实现与调试要点3.1 窗口收缩法的代码实现直接上代码我用 Python 写逻辑最清楚def find_closest_elements(arr, k, x): left, right 0, len(arr) - 1 while right - left 1 k: # 左边距离 右边距离时保留左边丢掉右边 if x - arr[left] arr[right] - x: right - 1 else: left 1 return arr[left:right 1]这个版本为什么不用abs()很多人第一次看会愣住。原因是数组有序当x落在数组区间内部时x - arr[left]和arr[right] - x都是非负的当x小于左端点时x - arr[left]是负数但此时它必然小于arr[right] - x所以条件成立执行right--也就是保留更靠近x的左端丢掉右端。反过来当x大于右端点时arr[right] - x是负数条件不成立执行left保留右端。所以这两个式子天然能表达“谁更远”的比较不需要额外取绝对值。再看一个例子arr [1, 2, 3, 4, 5]k 4x 3。初始left0, right4窗口长度 5。比较3-12和5-32相等保留左边right3窗口变成[1,2,3,4]。长度正好是 4返回[1,2,3,4]。这个结果符合题目“相等时选更小元素”的要求。如果比较条件写成if x - arr[left] arr[right] - x相等时就会执行left得到[2,3,4,5]在力扣上就会被判错。3.2 二分定位后左右扩散的参考实现如果你想对比可以看一下“内向外”的实现。这里我给出一个兼顾正确性和可读性的版本使用双端队列避免最后排序from collections import deque def find_closest_elements_center(arr, k, x): # 二分找第一个 x 的位置 lo, hi 0, len(arr) while lo hi: mid (lo hi) // 2 if arr[mid] x: lo mid 1 else: hi mid idx lo left, right idx - 1, idx res deque() while len(res) k: if left 0: res.append(arr[right]) right 1 elif right len(arr): res.appendleft(arr[left]) left - 1 elif x - arr[left] arr[right] - x: res.appendleft(arr[left]) left - 1 else: res.append(arr[right]) right 1 return list(res)注意这个版本中当左边更近或距离相等时把左边的元素放进结果头部右边更近时把右边的元素追加到尾部。这样利用双端队列天然保证结果升序省去最后sort的过程。但你必须小心翼翼处理left和right的移动顺序写错一个下标就会越界或者重复选元素。相比之下我还是推荐用 3.1 的收缩法面试时手写不容易出错。3.3 必踩的边界条件与常见错误这类双指针题目的 bug 通常集中在四个地方。第一k等于数组长度。此时窗口一开始就满足right - left 1 k循环一次都不执行直接返回整个数组。你的代码必须能处理这种情况不需要特判但要知道它不会崩。第二x小于数组最小值。比如arr [1, 2, 3, 4, 5]k 4x -1。收缩过程中比较-1 - 1 -2和5 - (-1) 6条件成立一直right--最终返回[1,2,3,4]。这是对的因为最小的几个数才最接近-1。第三x大于数组最大值。比如x 10那么比较时arr[right] - x是负数条件不成立一直left最终返回数组最后k个元素也是对的。第四数组里有大量重复元素。比如arr [1, 1, 1, 2, 2, 3]k 3x 1。初始left0, right5比较1-10和3-12条件成立right--继续收缩直到窗口变成[1,1,1]。因为相等时保留左边不会出现把1丢掉换成2的情况。注意很多网上题解在相等比较时写的是x - arr[left] arr[right] - x如果你只是抄代码很容易忽略等于号。等于号放在哪个分支直接决定输出“偏左”还是“偏右”。记住相等时保留左边等于号配合放在“丢右边”的分支里。4. 复杂度、变体与面试延伸4.1 两种双指针方案复杂度对比窗口收缩法的循环次数是n - k因为窗口从长度 n 缩小到 k每轮丢一个元素。时间复杂度 O(n - k)空间复杂度 O(1)。当k很小时接近 O(n)当k接近 n 时循环很少几乎 O(1)非常高效。二分定位后扩散的复杂度则取决于二分定位O(log n) 用于找插入位置再扩散 k 次所以总时间 O(log n k)。如果使用双端队列保存结果空间 O(k)。如果最后用sort实现还要额外 O(k log k)所以好的版本会用双端队列。还有一种更“高级”的二分写法直接对窗口左端点做二分。因为答案窗口的左边界l一定在[0, n-k]之间比较arr[l]和arr[lk]谁离x更远然后收缩左边界。这个解法时间复杂度只有 O(log(n-k))属于这道题的最优解但它更偏“二分”而不是“双指针”这里就不展开有兴趣可以自己推一下。4.2 变体数组无序、返回下标、求最小距离和面试官很喜欢在这道题基础上做变体。第一个变体数组不是有序的。那“结果连续”的性质就失效了双指针收缩法也没法直接用。此时要么先排序O(n log n)要么用堆或者快速选择Quickselect找前 k 个最接近的元素时间复杂度可以做到平均 O(n)。如果要求返回的 k 个元素保持原顺序快速选择后还需要额外标记或排序。第二个变体不返回元素值而是返回下标。这个其实更简单因为数组有序窗口收缩法里只需要记录 left 和 right最后返回list(range(left, right1))就行。第三个变体不是找最接近的 k 个而是求“最接近的 k 个元素的最小距离和”。这个等价于找到最优窗口后累加每个元素到 x 的绝对差。双指针收缩的过程中窗口会一直保持“当前长度下的最优”所以最后窗口的距离和就是最小距离和。你可以顺手在代码里加一个累加器验证一下。4.3 从这道题看懂双指针的一般套路双指针题目看起来五花八门但底层套路就那么几种。这道题属于“相向指针/收缩窗口”的类型特征是数组有序答案是需要保留一段连续区间通过不断排除不可能成为答案的端点来缩小范围。类似的题目还有“盛最多水的容器”“三数之和”“接雨水”它们都是利用有序性或单调性让两个指针朝着对方移动每次移动都排除掉一部分情况。遇到这类题先问自己三个问题数组是否有序答案是否是连续子数组比较两个端点时能不能唯一决定丢掉哪一边如果答案都是“是”那多半就是双指针收缩。另外还有一种“同向双指针/滑动窗口”适用于寻找最长子数组、满足条件的连续区间等问题和这道题不一样。很多初学者把两者混为一谈看到窗口就套模板结果边界条件写错。这里提醒一句滑动窗口通常维护一个窗口并移动右指针扩张、左指针收缩而这道题是“两端向内收缩”不要搞混。5. 常见问题与排查实录5.1 我的结果顺序为什么乱了如果你用的是“二分定位后左右扩散”并且最后用list.append的方式逐个添加元素顺序必然不是升序。因为从中间向外选先选到的是靠近中心的小元素再选到的是更左边或更右边的元素直接 append 会乱。解决办法有两个用双端队列从两端插入或者选完 k 个后对结果排序。我个人建议用双端队列因为排序会引入额外的 O(k log k) 复杂度而且容易在面试时被追问。如果用窗口收缩法返回切片arr[left:right1]天然有序不存在这个问题。如果你按索引一个个取出来再拼接也要注意别把顺序弄反。5.2 为什么比较距离不用 abs()这是评论区出现频率最高的问题。前面说过因为数组有序x - arr[left] arr[right] - x这个式子在处理“x 在数组外侧”时依然能给出正确的“保留更近端”的决策。不过要注意这种写法依赖数组有序而且必须保证left永远在right左边。如果你在循环里写错方向比如把左指针往右移、右指针往左移窗口会变成无效区间。每次移动后都要检查left right但收缩法的循环条件本身就是right - left 1 k所以不会越过放心写。如果你实在不放心也可以用绝对值abs(arr[left] - x) abs(arr[right] - x)结果完全一样但速度略慢一点点。面试时用哪种都行关键是能解释清楚相等时选哪边。5.3 自测用例自查表我把这道题常用的测试用例整理成一个表写完代码后照着跑一遍基本能覆盖所有边界情况。输入kx期望输出说明[1, 2, 3, 4, 5]43[1, 2, 3, 4]两侧距离相等选更小一边[1, 2, 3, 4, 5]4-1[1, 2, 3, 4]x 小于数组最小值[1, 2, 3, 4, 5]410[2, 3, 4, 5]x 大于数组最大值[1, 1, 1, 2, 2, 3]31[1, 1, 1]大量重复值靠左选择[0, 0, 1, 2, 3, 4]31[0, 1, 2]距离 1,0,1 与 0,1,2? 验证窗口整体更优[1, 2, 3, 4]12[2]k1 的退化场景[1, 2, 3, 4]4100[1, 2, 3, 4]k 等于数组长度跑这些用例时别只看输出还要检查输出顺序是否升序、长度是否为 k、相等距离时是否偏左。如果某个用例挂了建议先在纸上画出窗口收缩过程标记每次比较的左右端点和距离很快就能定位到是条件写反还是指针移动方向错了。我自己刷这道题时习惯先写暴力排序版本做验证再用双指针收缩法优化。这么做的好处是当你怀疑双指针逻辑有 bug 时可以拿暴力结果当“标准答案”对拍。对拍几组随机数据后心里就踏实了。这道题虽然不难但它是检验双指针基础是否扎实的一块试金石值得花半小时把它彻底吃透。
阅读完成 · 觉得有帮助？
