LeetCode 热题 100 题解2双指针一、什么是双指针在之前的讲解中我们探讨了哈希算法这一典型的“空间换时间”策略它通过额外存储空间实现 O(1) 时间复杂度的查询。本期我们将继续从入门开始学习双指针技巧——这种优化方法不需要额外存储空间仅通过两个指针的协同移动就能将暴力解法 O(n²) 的时间复杂度优化至 O(n)同时保持 O(1) 的空间复杂度。这种技巧是处理数组、链表和字符串问题的经典优化方案。在暴力法中我们会枚举所有可能的组合比如长度为 n 的数组两重循环需要枚举 n*(n-1)/2 种组合时间复杂度 O (n²)。而双指针在遍历序列时我们使用两个指针进行定向扫描通过指针的移动共同缩小搜索范围从而实现目标求解遍历数组只需 1~2 次总操作次数不超过 n时间复杂度稳定在 O (n)。双指针按照指针移动方向可以分为两大分支各自对应不同的解题场景。1.同向双指针快慢指针这种情况两个指针分为快指针和慢指针。两个指针从同一侧出发沿相同方向遍历快指针fast负责完整遍历整个序列完成元素筛选、条件判断慢指针slow负责锚定有效结果的存储位置通常只在遇到符合条件的元素时才向前移动。快指针移动速度快于慢指针适合需要原地修改数组或筛选元素的场景直接在输入的原始数据上做修改不额外开辟和输入规模成正比的新存储空间比如数组去重移动指定元素等也可以和链表结合应用于判断环形链表、寻找链表中点、寻找链表倒数第 k 个节点等这些内容会在以后的链表板块再做介绍。2.相向双指针对撞指针在这种情形下两个指针(left,right)分别从序列的左右两端出发向中间靠拢根据当前计算的结果决策移动左指针还是右指针逐步缩小搜索区间直到两指针相遇。这类解法通常依赖问题的单调性比如要求数组有序以保证移动指针的决策是正确的。它的典型应用场景有求和匹配类问题、接雨水问题等我们在之后的例题中具体分析。二、例题1.移动零本题要求原地修改数组把零移到末尾属于同向快慢双指针的入门模板题。当然如果不要求原地修改我们可以开辟一个新数组先遍历原数组将所有非零元素按顺序存入新数组再在尾部补零最后将新数组内容覆盖回原数组。这种辅助数组法虽然直观利于理解但还是开辟了和原数组同等大小的额外空间空间复杂度 O(n)。更优解法是同向快慢指针。把数字 0 放到末尾将序列中位于 0 之后的非零元素与最前面的 0 进行交换。基于这一思路我们就可以对快慢指针进行分工快指针fast每次移动一位完整遍历整个数组负责筛选出非零元素慢指针slow则标记下一个非零元素应存放的位置即最前面的 0 所在位置且仅在遇到有效非零元素时才向前移动。classSolution(object):defmoveZeroes(self,nums): :type nums: List[int] :rtype: None Do not return anything, modify nums in-place instead. slow0lengthlen(nums)# 快指针遍历筛选非零元素前移forfastinrange(length):ifnums[fast]!0:nums[fast],nums[slow]nums[slow],nums[fast]slow1该算法的时间复杂度为 O(n)其中快指针完整遍历数组一次尾部置零操作再遍历一次总体呈线性增长空间复杂度为 O(1)仅需使用两个指针变量无需额外的存储空间开销。同向双指针在原地修改数组的同时保证了元素原始先后顺序是对撞指针无法替代的特性。2.三数之和上期文章里我们讲解了两数之和问题利用哈希算法可以轻松实现反向查找但对于三数之和问题显然哈希已不再适用。从暴力遍历角度看这道题需要三重循环结构时间复杂度过高容易导致超时。我们进一步思考简化要想三数之和为零我们可以先对数组排序固定一个非正数作为基准再寻找另外两个与之匹配的数。这一步其实就巧妙地把三数之和问题降维成了有序数组两数之和的经典相向双指针问题把三层循环简化成了外层遍历 内层双指针。双指针的应用就很简单了将左右指针分别初始化为基准的右一位和数组末尾再计算三数之和与零大于零则将左指针右移小于零则将右指针左移当找到符合条件的组合时进行记录持续该过程直至左右指针相遇。重复上述操作直至遍历完所有小于等于零的基准数。同时题目要求不能有重复的三元组所以要注意跳过相同的值。classSolution(object):defthreeSum(self,nums): :type nums: List[int] :rtype: List[List[int]] nlen(nums)res[]# 边界长度不足3直接返回空ifn3:returnres# 排序双指针与去重的基础nums.sort()foriinrange(n):# 剪枝第一个数已大于0后续不可能凑出和为0ifnums[i]0:break# 第一层去重和前一个元素相同则跳过ifi0andnums[i]nums[i-1]:continue# 相向双指针初始化left,righti1,n-1whileleftright:totalnums[i]nums[left]nums[right]iftotal0:# 和偏小左指针右移增大数值left1eliftotal0:# 和偏大右指针左移减小数值right-1else:# 找到合法解加入结果集res.append([nums[i],nums[left],nums[right]])# 第二层左指针去重跳过连续相同值whileleftrightandnums[left]nums[left1]:left1# 第三层右指针去重跳过连续相同值whileleftrightandnums[right]nums[right-1]:right-1# 同步收缩指针寻找下一组解left1right-1returnres需要注意第一层去重时必须和前一个元素比较(nums[i] nums[i-1])与后一位比较可能漏解如[-1,-1,2]。如果遗漏二、三层去重则可能生成完全相同的三元组。该算法的时间复杂度为 O(n2)主要包括三个部分排序开销 O(nlog n)外层遍历 O(n)以及内层双指针遍历 O(n)整体呈现平方级的增长趋势空间复杂度为 O(log n)仅包含排序所需的栈空间开销结果存储不占用额外空间。3.盛最多水的容器盛最多水的容器是相向双指针 贪心思想的最典型代表。它无需数组排序仅依靠问题本身的几何性质就能通过双指针的定向移动将暴力 O (n²) 的复杂度压缩至 O (n)。任意两条垂线构成的容器盛水量由「两侧高度的较小值」和「两条线的水平间距」共同决定盛水量 min (height [left], height [right] ) × ( right - left )如果暴力枚举两层循环枚举所有可能的左右边界组合计算每一组的盛水量遍历全程记录最大值时间复杂度 O(n2)数组长度较大时超时。最优解法采用双向指针策略。初始时左右指针分别置于数组两端以获得最大宽度。核心操作是每次移动高度较低的一侧的指针其原理在于盛水量由较矮的板决定。若移动较高侧的指针宽度必然缩小而有效高度不会超过原短板的高度导致面积无法增大只有移动较矮侧的指针才可能遇到更高的板从而提升有效高度获得更大的盛水量。这一特性确保了我们可以安全地跳过所有移动高板的无意义组合。通过单次线性扫描即可找到最优解且不会遗漏最大盛水量的情况。classSolution(object):defmaxArea(self,height): :type height: List[int] :rtype: int left0rightlen(height)-1max_area0whileleftright:# 计算当前容器的盛水量valid_heightmin(height[left],height[right])widthright-left current_areavalid_height*width# 更新全局最大水量max_areamax(max_area,current_area)# 贪心决策移动更矮的一侧指针ifheight[left]height[right]:left1else:right-1returnmax_area这种算法时间复杂度为 O(n)左右指针仅需遍历数组一次每一步操作都能有效缩小搜索范围避免重复访问空间复杂度为 O(1)仅使用固定数量的变量无需额外存储空间完全满足原地操作的条件。4.接雨水作为双指针专题的经典难题接雨水是数组题型中的标杆之作。这道题目展现了从暴力解法到预处理优化再到双指针极致压缩的完整优化路径重点考察对问题本质的拆解能力和空间优化思维是面试中高频出现的困难级考点。本题的本质是逐位计算接水量再求和对于任意位置 i接水量由左右两侧最高柱子的「短板」决定位置 i 接水量 max (0, min ( 左侧最高柱高度右侧最高柱高度) - 当前柱高度 )当差值为负时说明当前柱子高于两侧挡板无法承接雨水接水量按 0 计算。我们可以先通过暴力法理解题意逐个遍历每个位置分别向左右扫描找到两侧的最大柱子高度代入核心公式计算当前位置接水量累加得到总水量。classSolution1(object):deftrap(self,height):nlen(height)res0foriinrange(n):# 找左侧最高柱left_max0forjinrange(i):left_maxmax(left_max,height[j])# 找右侧最高柱right_max0forjinrange(i1,n):right_maxmax(right_max,height[j])# 计算接水量watermin(left_max,right_max)-height[i]ifwater0:reswaterreturnres暴力法时间复杂度为O(n2)每个位置都需要向两侧完整扫描数据量大时严重超时。暴力法存在大量重复的最大值计算我们可以提前用两个数组预处理出每个位置的左右侧最大值消除重复遍历将时间复杂度降为线性。left_max[i]下标 i 左侧所有柱子的最大高度不包含 i 本身right_max[i]下标 i右侧所有柱子的最大高度不包含 i 本身classSolution(object):deftrap(self,height):nlen(height)ifn3:return0left_max[0]*n right_max[0]*n# 预处理左侧最大值数组foriinrange(1,n):left_max[i]max(left_max[i-1],height[i-1])# 预处理右侧最大值数组foriinrange(n-2,-1,-1):right_max[i]max(right_max[i1],height[i1])res0foriinrange(n):watermin(left_max[i],right_max[i])-height[i]ifwater0:reswaterreturnres动态规划优化用三次线性遍历完成预处理与结果计算将时间复杂度降到 O(n)。动态规划需要完整存储左右最大值数组而双指针可以将其压缩为两个变量。依靠左右指针的移动规律实时维护当前的左右侧最大值将空间复杂度从 O(n) 压缩至 O(1)。若 height[left] height[right]对于左指针位置右侧一定存在至少高度为 height[right] 的挡板因此该位置的水位上限由左侧最大值 left_max 决定计算后左指针右移若 height[left] height[right]同理右指针位置的水位上限由右侧最大值 right_max 决定计算后右指针左移。classSolution3(object):deftrap(self,height): :type height: List[int] :rtype: int lengthlen(height)left,right0,length-1l_maxr_max0res0whileleftright:ifheight[left]height[right]:ifheight[left]l_max:l_maxheight[left]else:resl_max-height[left]left1else:ifheight[right]r_max:r_maxheight[right]else:resr_max-height[right]right-1returnres指针从数组两端向中间靠拢每一步都由更矮的一侧负责计算和移动遇到更高的柱子就更新挡板高度遇到低洼位置就计算该位置能承接的雨水量。全程仅遍历数组一次指针相遇时计算结束最终累加值即为总接水量。三、总结双指针是处理数组与链表问题的经典优化技巧通过两个指针的协同遍历消除重复计算能在 O(1) 额外空间内将暴力解法 O(n²) 的时间复杂度优化至 O(n)。主要分为两类同向快慢指针和相向对撞指针分别适用于原地修改和区间搜索场景。本专题精选的四道题目全面展示了双指针的核心应用。移动零作为快慢指针入门题演示了原地筛选与元素重排的基础思想盛最多水的容器、三数之和与接雨水则层层递进地展现了相向指针的进阶应用从基于贪心的短板移动策略到结合排序降维与去重的综合技巧最终到极致空间优化的困难案例完整呈现了双指针利用单调性剪枝替代暴力枚举的核心算法逻辑。