双指针这个技术写到这一篇已经是第八篇了。前几篇我们聊过双指针的基础框架、左右指针和快慢指针的区别、滑动窗口的通用模板也穿插着处理过一些配合哈希表或者前缀和的题目。但很多读者在评论区反复问一个问题为什么有的双指针解法一眼就能看懂真到自己上手时却总是不知道指针该往哪边移动这一篇的关键词就俩字——单调性。它藏在这些题目最核心的位置正是因为有单调性双指针才能从“瞎枚举”变成“有方向地剪枝”复杂度才能从 O(n²) 压到 O(n)。这篇内容适合已经刷过一些双指针题、但总觉得“差一层窗户纸”的读者也适合准备面试时被追问“为什么这样做是对的”的朋友。1. 双指针里的“单调性”到底在说什么1.1 从两数之和的暴力优化看“省掉一半状态”先看一个最经典的场景数组numbers [1, 2, 3, 7, 9]要找两个下标使它们的和等于target 10。暴力解法谁都会写两层循环枚举i和j判断numbers[i] numbers[j] 10。可是暴力解法到底浪费在哪它没有任何信息可以用来排除下一次枚举。比如i 0时它还要去试j 1、2、3而实际上当j 4时1 9已经命中目标前面那几个中间结果虽然没命中它也没法提前说“往右走一定没有意义”。双指针做了什么呢L 0R n - 1此时numbers[L] numbers[R] 1 9 10直接就出答案。就算不出答案也有清晰的淘汰逻辑如果sum target说明当前右边已经贡献了能贡献的最大值升序数组中右边指针在最右端时值最大这个和还不够那左边这个L配任何右边位置的组合都不可能再更大了因为越往左的R值只可能更小。所以唯一该做的事是L。反过来sum target时说明左边已经是最小值可还是太大可做的只有R--。注意这里的关键不是“感觉该往哪边走”而是单调性决定了只有一侧可能有解另一侧的状态可以整片丢掉。1.2 单调性不是“数组递增”那么简单很多人以为单调性就是指数组有序。其实不止。更准确的说法是在指针移动过程中某个用来比较的判定值或者判定条件始终朝着同一个方向变化不会来回反复。两数之和里随着Lsum单调变大随着R--sum单调变小。比较对象是固定的target于是指针的移动方向就完全被“大于还是小于”决定。滑动窗口里也一样比如“窗口内元素个数”随右边界右移而增加、随左边界右移而减少这些量本身可能是单调的但真正重要的是它们对应的问题约束窗口一旦不合法扩大窗口只会更不合法所以必须收缩左边界。这些“不来回反复”的特性才是双指针剪枝能够安全进行的根本保证。所以你在写代码前可以问自己一句话如果我把一个指针朝某个方向移动剩下的候选解会变得更少还是更多如果我能证明“少掉的那部分里绝对不存在最优解”那这个方向就是安全的单调性成立双指针就能上。1.3 为什么复杂度能压到 O(n)很多初学者看到双指针代码觉得神奇明明只有一个循环套着一个循环的影子怎么复杂度就成了线性原因其实很朴素两个指针各自最多移动 n 次。左右夹逼模式下L从 0 到 n-1 单向走R从 n-1 到 0 单向走总移动次数不超过 2n滑动窗口模式下right从 0 到 n-1 走一趟left也从 0 到 n-1 走一趟同样是 2n。所谓 O(n²) 变成 O(n)并不是把内层循环删掉了而是把内层循环的枚举范围通过单调性证明直接剪裁掉每个状态不再重复访问。这样看复杂度分析其实比代码本身更重要。面试官问“时间复杂度为什么是 O(n)”你要把这句话讲清楚每个指针只会朝着一个方向移动每次移动都基于单调性的排除逻辑整体扫描量是线性的。2. 三类双指针模式先判断能不能用再写代码2.1 左右夹逼模式排序 可比较目标值这是大家最面熟的一类双指针。题目通常是在一个数组里选两个元素满足某种和、乘积、差等条件。朴素枚举是 O(n²)但如果数组有序比较结果会随指针移动单调变化。常用场景包括两数之和 II、三数之和、最接近的三数之和、盛最多水的容器。共同套路是先对数组排序如果题目允许再让左右指针分别从两端出发。这种模式成立的前提有三个第一问题允许重排数组有些题目要求返回下标那就不能直接排序要想其他办法第二比较目标和指针位置之间存在单调关系第三双指针移动的候选解空间可以无损剪枝。三数之和其实是两数之和的扩展固定第一个数剩下两个数仍然走左右夹逼排序保证内部左右指针对的“和”单调性不受影响。2.2 同向滑动窗口模式约束条件单调失效同向模式里两个指针都从一端出发一前一后共同维护一个“窗口”。典型场景是子数组、子串或者连续序列上的统计问题。窗口合法性的判断通常伴随一种规律右边界右移会让某个量变大或者让某个条件被破坏左边界右移会恢复合法性。比如“无重复字符的最长子串”中右指针扩展后如果重复了那继续扩展没有任何好处必须收缩左指针直到不重复。这类题写起来有个固定的直觉扩展右边界时更新窗口状态如果状态不合法就收缩左边界直到合法每轮更新答案。不要边扩展边随意收缩也不要在一个循环里同时移动左右指针那样会把单调性破坏掉陷入错乱。2.3 快慢指针模式空间有限所以必然相遇快慢指针是双指针的另一种常见形态用在判环、找链表中点、找重复数字这类场景。它和单调性的关系稍微隐晦一点——不是比较值单调而是“距离”在有限状态空间里被单向压缩。快指针走两步、慢指针走一步如果有环两者一定会进入环中并且相遇如果没有环快指针会先走到空。这类题不依赖排序也不依赖滑动窗口的约束合法性但要警惕空指针和环内死循环。本系列前几篇对快慢指针已经有详细拆解这一篇的重点还是放在左右夹逼和同向滑动窗口这两个与单调性最直接相关的模式上。当然“先判断模式”这个习惯是通用的拿到题目先想清楚属于哪一类再决定要不要排序、要不要额外数据结构。3. 六道经典单调性题型的完整拆解3.1 两数之和 II升序数组里的和判断题目要求给定一个升序排列的整数数组和一个目标值返回满足numbers[i] numbers[j] target的两个下标。双指针解法已经是标准答案func twoSum(numbers []int, target int) []int { l, r : 0, len(numbers)-1 for l r { sum : numbers[l] numbers[r] if sum target { return []int{l 1, r 1} } else if sum target { l } else { r-- } } return nil }要注意这里的边界条件l r不是l r。因为两个元素的下标不能相同。如果写成l r当l r时会把同一个元素用两次对很多测试用例会得出错误结果。我见过不少新手在这一步栽跟头建议在写之前先把“指针指向的元素能否重叠”想清楚。另外移动指针后不要立刻检查l是否越界循环条件已经保证了但你自己在调试时要清楚l最大只能到n-1。这个题的“单调性证明”可以这样讲若sum target由于数组升序右指针已经在可用的最大值上左指针不动的情况下往左移动右指针只会让和更小所以当前左指针位置不可能和右侧任何下标配出答案直接淘汰左指针左侧之前的所有状态L后重新判断。每一步淘汰一整段候选所以是 O(n)。3.2 盛最多水的容器移动矮边才有希望题目是在一个整数数组height中选两条线和 x 轴组成容器求能装的最大水量。两条线之间的面积公式是min(height[i], height[j]) * (j - i)。暴力解法枚举所有i j是 O(n²)双指针从两端往中间走func maxArea(height []int) int { l, r : 0, len(height)-1 ans : 0 for l r { area : min(height[l], height[r]) * (r - l) if area ans { ans area } if height[l] height[r] { l } else { r-- } } return ans }为什么移动更高的那一边没有意义因为面积由矮边决定如果固定矮边不动、把高边向中间移动宽度一定减小而矮边的高度不会因为这个移动变大所以面积不可能变大。反过来如果移动矮边新边界可能带来更高的边从而有机会增大面积。这个排除逻辑就是单调性的体现宽度随着任何一边内移都在单调缩小面积是否改善完全看边界高度是否足够“接替”成为更小的那一边。有人会纠结如果两边高度相等移动哪边常规实现移动右边但其实移动任意一边在数学上都不会丢失最优解因为相等时面积被任意一边限制移动一边后另一边的最大可能仍然能覆盖后续候选。你可以用一个小数组比如[1,8,6,2,5,4,8,3,7]手动推一遍把每一步指针位置和最大面积记下来就会很有感觉。3.3 三数之和排序 固定一数 双指针三数之和要求找出所有不重复的三元组使三个数之和为 0。最常用解法是排序后固定第一个数剩下两个数在右侧区间用左右夹逼。因为排序后三元素天然按大小排列重复元素也会相邻便于去重。def threeSum(nums): nums.sort() n len(nums) ans [] for i in range(n - 2): if i 0 and nums[i] nums[i-1]: continue l, r i 1, n - 1 while l r: total nums[i] nums[l] nums[r] if total 0: ans.append([nums[i], nums[l], nums[r]]) while l r and nums[l] nums[l1]: l 1 while l r and nums[r] nums[r-1]: r - 1 l 1 r - 1 elif total 0: l 1 else: r - 1 return ans这里最容易踩的坑是去重逻辑。很多刚接触的人会在找到答案后直接l 1; r - 1结果遇到[-1, -1, 0, 1]这类数组时输出重复三元组。正确做法是先把相邻重复值跳过再移动指针。还有外层i的去重要用nums[i] nums[i-1]而不是nums[i] nums[i1]因为后者会错误地把已经固定住的第一位元素也跳过。这一点面试里经常被追问值得刻意记一下。复杂度上排序是 O(n log n)外层循环 n 次内层双指针扫描 O(n)整体 O(n²)。这可以理解为“固定一个维度后剩余二维问题被单调性剪枝成线性”。3.4 无重复字符的最长子串同向窗口维护合法性最长子串问题要求找到不含重复字符的最长子串长度。常用滑动窗口右指针不断扩展同时用哈希表或者数组记录字符出现次数一旦某个字符出现次数大于 1就移动左指针收缩窗口直到整个窗口重新合法。func lengthOfLongestSubstring(s string) int { cnt : make(map[byte]int) left, ans : 0, 0 for right : 0; right len(s); right { cnt[s[right]] for cnt[s[right]] 1 { cnt[s[left]]-- left } if right-left1 ans { ans right - left 1 } } return ans }为什么能不用哈希表计数然后暴力验证所有子串因为窗口的“重复状态”是单调的右边界向右扩展只会增加字符计数不可能自动消除重复所以一旦出现重复唯一让窗口恢复合法的方式就是移动左边界。这个“右扩展触发不合法左收缩恢复合法”的循环就是滑动窗口版本的单调性。每次right移动后内层left最多连续移动若干步但总和依然不会超过 n所以整体 O(n)。很多初学者在更新答案时容易放在收缩之后其实放在每轮循环末尾即可。因为左指针收缩后窗口会变短但这一段收缩后的窗口同样可能是合法最长必须参与比较。还有一个细节如果字符串里只包含小写字母可以用大小为 256 的数组代替哈希表速度会更快面试时可以提这个优化。3.5 长度最小的子数组窗口合法就收缩题目给一个正整数数组和一个目标值target找出满足和不小于target的连续子数组的最小长度。这个题是滑动窗口里和单调性结合得最直接的一道右指针每扩展一步如果窗口内元素和已经大于等于目标那么右指针再往右只会让子数组更长不可能得到更小解所以此时必须尝试移动左指针收缩窗口并持续更新最小长度。func minSubArrayLen(target int, nums []int) int { left, total : 0, 0 ans : int(^uint(0) 1) for right : 0; right len(nums); right { total nums[right] for total target { if right-left1 ans { ans right - left 1 } total - nums[left] left } } if ans int(^uint(0)1) { return 0 } return ans }注意数组必须是正整数。为什么因为只有数值为正时扩大到窗口才能保证 sum 单调不减才有“继续扩展没有意义”的结论。一旦数组里有负数这个单调性就失效了滑动窗口不能直接用需要转成前缀和加哈希表或者其他结构。这个反例非常经典我建议你亲手跑一遍才记得牢。3.6 最大连续 1 的个数 III允许翻转 0 的等价视角这道题说的是给定一个二进制数组最多可以把k个 0 翻转成 1求最长连续 1 子数组的长度。直接想“翻哪些 0”会让人卡住但换个角度就清晰了等价于找一个最长子数组里面 0 的数量不超过k。这个问题立刻进入滑动窗口射程窗口内统计 0 的数量超过k时收缩左边界直到 0 的数量重新合法。def longestOnes(nums, k): left 0 zero_cnt 0 ans 0 for right in range(len(nums)): if nums[right] 0: zero_cnt 1 while zero_cnt k: if nums[left] 0: zero_cnt - 1 left 1 ans max(ans, right - left 1) return ans这道题的价值在于它展示了一个通用的转化思路把复杂操作等价成对某个统计量的约束再借助单调性剪枝。面试中如果遇到“看起来要模拟很多状态”的滑动窗口题先尝试把条件改写成一个可以随窗口边界单调变化的量思路会顺畅很多。4. 识别单调性动手前先画一条状态转移线4.1 三步判断法能不能排序条件是否单向剪枝安全吗很多读者会问我也知道要用双指针可我不知道什么时候该用、什么时候不该用。我一般建议三步走。第一步看问题能不能排序。这里指的不是题目里数组原本是否有序而是排序是否会破坏你要的答案。比如要返回三元组的数值本身而不是下标排序后就完全可行如果要求返回下标那排序就需要额外记录原始下标处理起来变复杂。第二步看比较条件是否随指针移动单向变化。拿两数之和来说和值随着左指针右移单向上升、随着右指针左移单向下降这就是典型的单向变化。如果条件会来回震荡比如数组有负数导致前缀和乱跳那双指针就危险了。第三步确认被剪掉的状态里确实没有最优解。这一步必须能说清理由哪怕只是列举几个反例让自己安心。这三点都满足基本可以放心写双指针。这个判断过程其实是在给代码做正向验证而不是写完再测试。我个人的习惯是先在草稿纸上画一根数轴把指针当前位置、候选解可能存在的区间、需要剪掉的方向标出来再落笔写循环。这个习惯帮我避开了很多“能跑但一换数据就错”的问题。4.2 什么时候双指针不适用负值、无序、条件复杂先说不适用的情况避免踩坑。第一类无序且要求返回下标的两数之和双指针不能直接排序唯一的线性做法是哈希表或者用带原下标的排序加双指针兜底但那也要先处理下标。第二类数组含负数时的连续子数组和问题滑动窗口的正数前提被打破非法窗口收缩的逻辑不再正确。第三类区间最值问题如果统计量不是单调增减比如要在窗口里维护一个“聚成一团”的奇怪条件双指针也无法保证安全剪枝。面试难题往往就藏在第二类和第三类里。比如求“和为 k 的子数组个数”即使目标固定只要数组里出现负数窗口左右移动时和值会来回跳你就不能用双指针。应该改用前缀和加哈希表复杂度依然是 O(n)但依赖的是“前缀和相减得到子数组和”的数学关系而不是单调性。能区分“什么时候用双指针什么时候换成哈希表”是区分算法入门和进阶的很典型标志。4.3 用最小用例验证单调性写完代码以后别急着提交到在线评测系统。先用一个小数组手动推一遍临界情况。比如两数之和可以用[1,2,3,4]这种连续升序数组检查 target 是左端命中、右端命中、中间命中、完全不存在的几种情况。滑动窗口可以用一个只有两个字符的字符串像aaaa这种极端重复的用例跑一遍看收缩逻辑是否正确。我常用的方法是打印每个关键分支的指针位置和当前窗口状态。程序能跑通只是第一步更重要是看得懂每一步为什么这样移动。打印中间状态这件事对初学者理解双指针的单调性特别有帮助尤其能在你读不懂别人题解时让你自己把代码执行过程看清楚。5. 常见错误与排坑实录问题表现根本原因解决方式三数之和输出重复三元组找到答案后没有跳过相邻重复值答案处增加while跳过左右两边的重复项再做指针移动两数之和返回了相同下标循环条件写成l r改成l r保证两个下标不同滑动窗口求最短不更新答案把答案更新放在收缩之前每轮窗口合法后统一点更新或者收缩完后单独比较数组有负数时滑动窗口出错正数前提不成立窗口扩缩和值不单调换前缀和哈希表不要硬套双指针无重复字符最长串输出错误字符计数更新时机不对右指针移动后先更新计数再判断是否收缩不能先收缩再更新计数上面的表格是从实际刷题里总结出来的几乎每个过这篇内容的人都会碰到其中一两个问题。写双指针题的代码往往很短但短代码出错时的隐蔽性很强。你提交后如果某个用例挂掉第一步不要查循环逻辑先检查指针移动后有没有更新对应的计数或累加值。比如滑动窗口漏掉cnt[s[left]]--这行代码可能是最长子串题里最容易漏的一行。还有一类问题是“指针停不下来”。通常是某个分支没有推进指针比如两数之和里sum target找到答案后直接返回倒还好但三数之和里找到答案后如果没有同时移动左右指针下一轮会重复检查同一组坐标导致死循环。这个坑很常见建议在代码里形成条件反射只要找到了合法组合左右指针必须至少移动一个。6. 训练方法与实战心得这一篇算是把单调性这个概念在双指针里的作用讲透了。如果你正处在刷题阶段我建议的练习顺序是这样先把我上面六个经典题自己写一遍不追求速度但要能在每题完成后清楚说出“为什么舍弃另一边指针是安全的”。写完再动手做三数之和的变体、接雨水这类组题把证明过程变成习惯。从我自己的经验看刷双指针题最容易成长的时间点其实不是在“会写正确代码”那刻而是卡壳后想通“哇这里的状态原来可以整个放弃”的瞬间。那一下想通才是把双指针从“背模板”升级成“理解算法”的关键。把这几题的单调性证明写在笔记里过两天再回头看一次比你连续刷二十道同类型题目更有效。如果你准备面试还有一个额外建议把“为什么时间复杂度是 O(n)”当成送分题来准备。很多面试官不会满足于你说“因为有两个指针”而是要听到“因为每个指针单向移动合并剪枝后总状态数为 O(n)”。这道送分题答得漂亮能给面试官留下很扎实的印象。希望你把这篇文章里的单调性真正理解成自己的判断力而不只是记下几段模板代码。