★ FEATURED ARTICLE 做算法题的时候双指针是我最先掌握、也最容易被它迷惑的技巧之一。而真正让我把这一块学明白的是最终理解了它背后的单调性。如果说双指针是招式那单调性就是心法。这个双指针专题走到第7篇前面聊过相向、同向、滑动窗口这些具体模板这篇想把大家最关心的一个问题讲透为什么双指针能省掉那么多无效遍历为什么有的题目天生适合双指针而有的题目一用就错这篇内容不挑基础就是从一个从业者的视角把双指针为什么会高效拆开揉碎。不管你是面试前临时抱佛脚还是在系统刷题中期想突破瓶颈理解单调性这一层之后你会发现自己判断一道题能不能用双指针的准确率明显上升。后面我配了五道完整的手把手拆解代码可以直接照着写也标注了我自己踩过的坑希望能帮你省下不少走弯路的时间。1. 双指针的单调性到底是什么1.1 从两数之和开始移动指针时发生了什么先看最经典的场景在一个升序数组里找两个数使它们的和等于目标值target。暴力做法谁都会两层循环枚举所有组合复杂度O(n^2)。双指针的做法是左指针left指向数组头右指针right指向数组尾计算sum numbers[left] numbers[right]。如果sum等于target直接返回如果sum比target大right往左移动一步如果sum比target小left往右移动一步。这个流程背下来很容易但很多人没想过一个问题凭什么移动指针就能保证不遗漏正确答案我举个例子你就明白了。假设数组是[1, 3, 5, 8, 12]target是13。初始left在1right在12sum等于13正好命中。那如果target是9呢初始sum是11213大于9于是right左移。为什么right敢左移因为此时1是当前区间里最小的数1加12都已经超过target那换成区间里其他数和12相加结果只会更大更不可能等于9。换句话说在当前这一轮里12这个元素可以被彻底排除掉后面无论left怎么移动都不会再需要它。反过来如果sum小于target比如数组变成了[1, 3, 5, 8, 9]target是9初始sum是1910大于9右移假如换一个场景sum小于target那就说明当前区间里最大的数配上left都已经不够大left这个元素也可以被彻底排除。每次排除一个元素指针单向移动这就是双指针能保证O(n)复杂度的根本逻辑。1.2 单调性的本质单向排除不回头我之前在带人刷题时发现一个共性很多人会把双指针理解为两头往中间找答案的搜索方法这个理解不能说错但没抓到要害。双指针的真正内核是一种单向排除策略每一轮迭代至少有一个指针向前推进而被推进的那个指针所指向的元素从此退出后续所有候选集合不会再被访问。想得再直白一点整个搜索空间是一条从左到右的序列左右两个指针像剪刀一样一口一口把序列两侧的不可能元素剪掉每次剪掉之后就绝对不会再捡回来。为什么这个策略有效因为它依赖一个看不见的前提——问题的状态必须在某个方向上具备可比较、可传导的性质。上面两数之和的例子中和的大小随着left右移而增大、随着right左移而减小这种关系就像一条平滑的曲线你知道某个点已经越过目标后它后面的点也没希望了。工作里我会把这个性质叫作决策单调性。这是双指针所有变体的公共底座相向双指针要求两个指针各自移动时答案的优劣是单调变化的同向双指针要求边界扩张和收缩时窗口的合法性是单调变化的。没有这个底座双指针就会漏解甚至陷入死循环。1.3 三种常见的单调性形态理解了本质我们再把具体题目归纳一下。当你拿到一道题可以从下面三个角度去检查它是否具备双指针的单调性。第一种是数值单调。数组本身就是有序的或者我们可以通过排序让数组有序。数值有序之后指标比如和、积、差和指针位置之间的关系就变得可预测。两数之和、三数之和都属于这一类。第二种是决策单调。状态之间不一定存在显式的数值大小但存在一个单调变化的判断条件。比如盛最多水的容器面积 min(height[left], height[right]) * 宽度如果左边柱子的高度更矮那么无论right怎么移动只要left保持不变面积都不可能变大因此left只能右移。这就是一种由不等式推导出来的单调排除。第三种是窗口合法性单调。滑动窗口是一类特殊的双指针right向右扩展窗口left向右收缩窗口。当right每向右多容纳一个元素窗口的非法程度只增不减所以一旦非法只能靠left收缩来恢复合法性。这个合法性随right单调变化的性质保证了left不需要回退整体复杂度才能控制在O(n)。看到这里你应该明白了单调性不是题目里明说的一个条件而是我们分析问题时找到的一条隐含线索。找到它的那一瞬间O(n^2)的暴力解就能改写成O(n)的双指针解。2. 怎么快速认出这是一道单调性双指针题2.1 相向双指针有序数组上的对撞相向双指针的特征非常明显left从0开始right从n-1开始两个指针向中间靠拢。几乎所有的这类题都有两个信号。第一个信号是题目里存在两个独立元素之间的关系比如找两个数满足某个条件求两堵墙最多能盛多少水判断字符串是否是回文。两个元素的组合天然适合用两个指针去表示。第二个信号是移动的决策可以由当前两个指针位置直接算出。注意这里的算出不是暴力枚举而是通过比较当前状态下左指针能贡献多少、右指针能贡献多少来决定移动方向。两数之和里比较sum和target的大小盛水容器里比较height[left]和height[right]的高矮回文判定里比较两端字符是否相等都是这个思路。所以以后看到两个变量、一个关系式、可以排序的题目你可以在草稿纸上画一条线段左右各放一个指针先模拟一轮判断看看被丢弃的那一侧是否真的没有利用价值。只要一轮排除是安全的整道题基本就能用双指针走通。2.2 同向双指针滑动窗口的合法性伸缩同向双指针或者叫滑动窗口话题里经常单独成篇这里只讲它和单调性之间的联系。它的形态是left和right都从0出发right向右扩张当窗口不满足某个约束时left向右收缩直到窗口重新合法。这类题有一个共性约束条件针对的是连续区间。比如最长无重复子串要求窗口内字符不重复长度最小子数组要求窗口内数字之和至少为target。连续区间的问题用前后两个下标表示天然比枚举所有(i, j)组合要省事。判断能不能用滑动窗口的要点是right扩张会不会让窗口变得更差left收缩会不会让窗口变得更好。如果答案都是肯定的就说明窗口状态的变化是单调的可以放心使用。反过来如果right右移可能让窗口变好、也可能变坏那滑动窗口就不适用往往需要引入更复杂的数据结构。2.3 先排序再双指针给数据造出单调性这一招在两数之和的变体里尤其常见。原始数组如果无序双指针的所有推导都失效了因为left右移时数组值可能变大也可能变小你无法判断该移动哪个指针。解决办法很朴素就是先排序。排序的代价是O(nlogn)换来的是O(n)的扫描整体还是比暴力O(n^2)划算。三数之和、四数之和、最接近目标值的三数之和、三角形计数这类题都是先排序再双指针的典型。我特别想提醒的是排序之后原数组的下标信息会丢失。如果题目最终要求输出的是元素值本身那无所谓如果要输出原数组下标就得在排序前额外记录每个元素的位置。这个问题我见过不少人栽跟头后面常见问题部分会再展开。2.4 反向思维用边界比较构造单调判断有些题目没有显式的排序也没有区间合法性这种容易量化的状态但依然可以用双指针。关键是找到边界上谁说了算的依据。以接雨水为例某个位置能接多少水要看它左右两边最高柱子中较矮的那根。如果用暴力思路每个位置都要往左右各扫描一遍复杂度O(n^2)。双指针的解法则是在两个指针处分别记录left_max和right_max然后比较当前两根柱子的高低哪边矮就先处理哪一边。因为对于矮的这一边来说它能盛多少水已经由对面那侧的已知最大值锁定了不用担心未知区域的影响。这种从两端向内逐步确定答案的方式本质上也是一种单调排除每次处理完后那个位置就确定下来不再需要回头。所以识别双指针时不要把思路困在数组必须先有序上更灵活的标准是你能不能找到一个安全规则每次推进一个指针同时确定一部分答案。能就能用双指针。3. 专题7实操五道题把单调性用透3.1 两数之和有序版最干净的对撞模板题目背景给定一个升序数组和一个目标值target找出两个数使它们之和等于target返回两个数的下标下标从1开始。思路其实在上面已经推导过了这里直接给代码然后强调几个容易写错的地方。def twoSum(numbers, target): left, right 0, len(numbers) - 1 while left right: s numbers[left] numbers[right] if s target: return [left 1, right 1] elif s target: left 1 else: right - 1 return [-1, -1]这个模板的三个要点。第一循环条件必须写成left right不能带等号。因为题目要求使用两个不同的元素left等于right时对应同一个位置这个状态没有意义。如果题目允许同一个元素用两次才需要考虑带等号的情况。第二else分支的顺序。很多初学者会在s target之后写if s target和else但严格来说应该先判断小于再判断大于或者反过来都行关键是不要漏掉相等分支否则逻辑会残缺。第三移动方向不要搞反。s小于target时说明数组当前边界太小应该让left右移去增大和s大于target时说明两个数之和太大应该让right左移去减小和。可以这么记指针移动方向永远是让当前指标朝target方向逼近。这道题是相向双指针的基石后面的三数之和、最接近的三数之和、四数之和本质上都是在这个模板外面套一层循环。3.2 三数之和排序加双指针难点全在去重题目背景给定一个整数数组nums判断是否存在三个元素a、b、c使得abc0找出所有不重复的三元组。这题比两数之和难的地方有两点一是需要先固定一个数再对剩下两个数用双指针二是结果要避免重复三元组。先排序然后外层循环固定nums[i]内层在i1到n-1区间内用双指针找两数之和等于-nums[i]。整体代码如下。def threeSum(nums): nums.sort() n len(nums) res [] for i in range(n - 2): if nums[i] 0: break if i 0 and nums[i] nums[i - 1]: continue left, right i 1, n - 1 while left right: s nums[i] nums[left] nums[right] if s 0: res.append([nums[i], nums[left], nums[right]]) left 1 right - 1 while left right and nums[left] nums[left - 1]: left 1 while left right and nums[right] nums[right 1]: right - 1 elif s 0: left 1 else: right - 1 return res去重是我最想讲的部分。第一层去重发生在固定nums[i]时如果nums[i]和nums[i-1]相等跳过。为什么是和i-1比而不是和i1比因为我们要保证同一个数值只在第一轮被固定一次。比如数组是[-1, -1, 0, 1]如果中途跳出第一个-1直接用第二个-1就会生成重复的三元组[-1, 0, 1]。和i-1比较意味着跳过的是从第二个开始的所有重复值而第一个值仍然会被处理。第二层去重发生在找到一组答案之后。此时left和right都已经移动我们需要跳过所有和刚刚使用过的值相等的元素。这里要特别注意去重和移动的顺序先left加一、right减一再检查新位置是否和前一个位置值相等而不是先判断再移动。否则容易跳过有效组合或者造成死循环。另外当s小于0时只需要left加一当s大于0时只需要right减一这两种情况下不需要去重检查因为即使后续遇到重复值也会在找到答案后的去重阶段统一处理。3.3 盛最多水的容器为什么移动短边题目背景给定一个非负整数数组heightheight[i]表示第i条垂直线的长度选择两条线使得它们与x轴共同构成的容器能容纳最多水。面积的计算公式是width乘以较短边高度即area min(height[left], height[right]) * (right - left)。初始时left在最左端right在最右端此时宽度最大。接下来每一步都要决定移动哪一边。很多人会凭直觉说应该移动较短的那条边但没想过为什么。我们严格推导一下假设height[left] height[right]那么当前面积由height[left]决定。如果此时我们移动right新的宽度一定更小而高度仍然受限于height[left]所以新面积一定小于等于当前面积。也就是说移动right这一侧永远不会得到更优解可以直接排除。反过来移动left则有可能遇到更高的柱子从而让面积增大。代码非常简洁。def maxArea(height): left, right 0, len(height) - 1 ans 0 while left right: area min(height[left], height[right]) * (right - left) ans max(ans, area) if height[left] height[right]: left 1 else: right - 1 return ans这里的相等情况也很关键当height[left]等于height[right]时移动哪一边都可以因为两边作为瓶颈的效果一样。常见写法是移动左边也有写成移动右边的都能通过。这道题给我们的启发是双指针不一定要求数组有序只要求移动一侧不可能更优这个单调判断成立。以后遇到几何、容量、距离相关的优化题优先想一想短边原理这类启发式规则。3.4 无重复字符的最长子串滑动窗口的合法区间维护题目背景给定一个字符串s找出其中不含重复字符的最长子串长度。这是一道同向双指针或者说滑动窗口的经典题。right逐个向右扩展窗口把新字符加入窗口如果窗口内出现了重复字符说明当前窗口不合法就需要让left向左收缩窗口直到重复字符被排除。def lengthOfLongestSubstring(s): seen set() left 0 ans 0 for right, ch in enumerate(s): while ch in seen: seen.remove(s[left]) left 1 seen.add(ch) ans max(ans, right - left 1) return ans代码的逻辑核心在while循环一旦当前字符ch已经在窗口集合里就重复执行移除最左边的字符、left加一。注意这里用的是while而不是if因为窗口里可能包含多个与ch重复的字符吗其实不会一个字符在窗口里最多出现重复一次才会触发条件所以理论上if也可以但用while更安全防止窗口在连续收缩时仍然不合法的情况。另一个细节是left移动时要移除的是s[left]而不是重复的那个字符。因为我们维护的是窗口的连续性窗口是[left, right]这段区间所以收缩时必须从最左边开始丢弃才能保持窗口内元素仍然对应一段连续子串。这道题的单调性体现在哪里right每向前扩展一格窗口内的字符种类只会增加或不变重复的可能性也只会增加也就是说窗口非法这个状态是单调变差的而left收缩让窗口重新合法的过程就是逆着这个单调方向修复状态。正因为这种单调性left移动的总次数不会超过n整体复杂度才是O(n)。3.5 接雨水双指针的逆向使用题目背景给定n个非负整数表示宽度为1的柱子的高度图计算按此排列的柱子能接多少雨水。接雨水有很多解法单调栈、动态规划都可以双指针是其中代码最紧凑的一种。思想是某个柱子能接的水量取决于它左右两侧最高柱子中较矮的那一根。维护两个指针分别从左右向中间扫描同时记录左侧最大值left_max和右侧最大值right_max。def trap(height): left, right 0, len(height) - 1 left_max right_max 0 ans 0 while left right: left_max max(left_max, height[left]) right_max max(right_max, height[right]) if height[left] height[right]: ans left_max - height[left] left 1 else: ans right_max - height[right] right - 1 return ans这段代码有个很容易误解的地方为什么当height[left] height[right]时可以直接认定left位置的水量由left_max决定因为对于left位置来说它右侧的最高柱子一定不低于height[right]而left_max是已经扫描过的左侧最高值。如果height[left]比较矮说明当前柱子的水量瓶颈来自左侧此时right侧无论还有多高的柱子都不会改变矮的一侧限高这个事实。所以先处理矮的一侧答案确定后让指针向内收缩这是非常标准的安全排除策略。while条件同样是left right因为最两端的柱子不可能储水当两个指针相遇时处理结束。这个解法的时间复杂度O(n)空间复杂度O(1)比动态规划需要两个数组的做法省了很多内存是我在实际场景里优先推荐的双指针写法。3.6 验证理解的几个改编问题如果上面的题目你都看懂了可以试着在脑子里过一遍这些改编第一两数之和把和等于target改成和最接近target双指针还能用吗能用只需在每次计算和时更新最优答案即可。第二三数之和把等于0改成最接近target同样在循环里多一步记录最优差。第三盛最多水的容器改成求能装最多水的三个柱子组合就不能简单用双指针了因为多了一个维度。如果你能准确说出第三题为什么不能套用时说明你真的理解了单调性的边界。4. 实战中容易踩的坑与排查方法4.1 边界条件与死循环问题双指针写的死循环多半是循环条件或者指针更新步长出了问题。比如两数之和把循环条件写成left right而数组里恰好存在一个取值使得2 * numbers[mid]等于target时就会错误地返回同一个下标两次。当然很多实现里返回前根本没检查下标不同于是错误结果被当成正确答案输出。检查这类问题的方法很笨但有效在草稿纸上手动模拟一个长度为4或5的数组把每一轮left、right、sum的取值都写下来通常会在一分钟内定位问题。另一个死循环来源是找到答案后忘记同步更新两个指针。像三数之和如果找到一组零三元组后只执行left加一或者只执行right减一下一次计算时又遇到同样的值就可能一直原地打转。我的习惯是找到答案的那个分支里两个指针必须同时移动然后再做去重。4.2 去重和指针更新顺序的细节去重顺序的问题非常隐蔽。在找答案后的去重循环里我见过有人这样写while left right and nums[left] nums[left 1]: left 1 left 1这种写法的问题在于如果数组末尾全部是重复元素left可能一路跳到right然后最后的left加一就让left超过了right下一轮循环条件虽然会拦住但逻辑上已经产生了越界访问的风险。更稳妥的是我之前代码里的写法先left加一再判断新位置是否和旧位置重复继续跳过。另一个去重细节在第一层固定元素时一定要等i到等于某个值但未处理过时处理然后跳过后面所有相同的值。也就是说去重使用的是nums[i] nums[i-1]的判断而不是nums[i] nums[i1]。写成后者你会错误地跳过第一次出现的值导致漏解。4.3 指针更新顺序错误有些题在更新指针之前需要先取旧指针位置的值参与计算比如盛水容器。如果你先移动了指针再计算面积面积的老宽度就没了结果必然错误。我建议在写代码时把顺序固定成三层逻辑先计算当前状态下的候选答案再根据单调性判断移动哪个指针最后在需要时进行去重或额外更新。这样顺序清晰不容易漏。尤其是滑动窗口类题目right每轮扩充一次left可能在循环里连续收缩多次顺序稍有差错窗口的区间就不连续了。4.4 排序会改变原数组需要保存下标吗当题目要求返回原数组下标时排序会破坏下标信息必须提前处理。推荐的做法是用一个额外数组存下标排序的时候按照值排序同时把下标一起带上或者干脆定义一个元组列表每个元素是(value, index)排序时按value排。这个问题在两数之和无序版本里非常常见。如果你先排序然后双指针找到了正确数值却返回了排序后的下标结果必然是错的。更合理的方案其实是无序两数之和直接用哈希表一遍遍历解决不需要排序。但如果是三数之和这类必须排序的题目就要时刻记住返回值里只有元素值没有下标要求。4.5 常见问题速查表现象可能原因修复方向死循环或超时循环条件写错或者指针没有同步更新检查left是否每次都朝right方向移动right是否每次都朝left方向移动输出重复答案去重逻辑缺失或去重顺序错误固定元素去重比较i和i-1找到答案后先移动指针再跳过重复值漏掉有效答案去重写成了跳过第一次出现的值去重时不要跳过第一次出现的值只跳过后续相同的值返回错误下标排序后没有保留原下标用(value, index)结构排序或者改用哈希表解法越界访问while条件里left或right已经越过边界所有while内层循环都要加上left right条件移动方向反了对单调性判断不熟回到第1章用排除法逻辑重新推导一次5. 从双指针到算法直觉单调性还能用在哪5.1 二分查找单调性划走半边搜索空间很多人不知道二分查找的本质也是一种单调性排除因为数组有序所以当中间值大于目标值时可以确定目标只可能出现在左半边于是把右半边整个排除。这和双指针的排除法逻辑是同源的都是利用单调信息剪枝。区别在于二分查找每次排除一半空间而双指针每次排除一个元素。所以二分查找的复杂度是O(logn)双指针是O(n)。如果遇到一个有序数组而且你要找的不是单一目标值而是两个元素之间的关系就要优先想到双指针如果找一个元素的位置二分更合适。两者搭配好能覆盖很大一类面试题。5.2 单调栈与单调队列维护单调信息单调栈也是单调性的近亲。比如接雨水、每日温度、柱状图中最大的矩形这些问题都需要维护一个单调递增或递减的元素序列利用当前位置被某个边界限制的规律来快速计算答案。双指针和单调栈的区别在于双指针通常处理的是序列两端的关系适合双向收敛单调栈处理的是序列中下一个更大/更小元素的关系适合单向扫描。当你在做一道题时发现需要关注某个元素左边第一个比它小的位置这类信息就应该从双指针切换到单调栈的思路。5.3 怎么判断一道新题能不能用双指针我把自己的判断流程分享出来你以后可以直接抄作业。第一步把题目写成暴力枚举的形式看看候选答案是否由两个位置决定。第二步尝试让一个指针单方向移动问自己当前状态下移动哪一侧不会错过最优解如果能给出严格的不等式推导说明存在单调性。第三步检查指针移动的总次数是否线性如果是双指针方案基本成立。这三个步骤看着简单但能规范解决掉大半纠结。我见过太多人拿到题先套模板结果相向套到滑动窗口上自然怎么调都过不了。先判断单调性再决定用哪种双指针形态顺序不能反。另外还有一个经验把做过的双指针题按相向、同向、先排序、边界比较四个小类归档比按题目难度归档有用得多。因为同一类背后是同一套单调性推导复习时大脑回忆的负担会小很多。我自己刷到后期基本能做到看到题先归入其中一类再用对应模板快速写出主线代码正确率比过去乱刷时高了不止一个档次。回到开头的那个问题为什么双指针那么快因为单调性让候选空间在每一步都确定性地萎缩而不是靠运气去碰撞答案。把这个心法真正装进脑子里双指针对你来说就不再是零散的一堆模板而是一条贯穿始终的思路线。希望这篇专题7能帮你在算法路上往前再扎实走一步。
阅读完成 · 觉得有帮助？
