企业官网建设流程全解析

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. """slow=0length=len(nums)# 快指针遍历，筛选非零元素前移forfastinrange(length):ifnums[fast]!=0:nums[fast],nums[slow]=nums[slow],nums[fast]slow+=1

该算法的时间复杂度为 O(n)，其中快指针完整遍历数组一次，尾部置零操作再遍历一次，总体呈线性增长；空间复杂度为 O(1)，仅需使用两个指针变量，无需额外的存储空间开销。同向双指针在原地修改数组的同时，保证了元素原始先后顺序，是对撞指针无法替代的特性。

2.三数之和

上期文章里我们讲解了两数之和问题，利用哈希算法可以轻松实现反向查找，但对于三数之和问题显然哈希已不再适用。
从暴力遍历角度看，这道题需要三重循环结构，时间复杂度过高容易导致超时。我们进一步思考简化，要想三数之和为零，我们可以先对数组排序，固定一个非正数作为基准，再寻找另外两个与之匹配的数。这一步其实就巧妙地把三数之和问题降维成了有序数组两数之和的经典相向双指针问题，把三层循环简化成了外层遍历 + 内层双指针。
双指针的应用就很简单了，将左右指针分别初始化为基准的右一位和数组末尾，再计算三数之和与零，大于零则将左指针右移，小于零则将右指针左移，当找到符合条件的组合时进行记录，持续该过程直至左右指针相遇。重复上述操作，直至遍历完所有小于等于零的基准数。同时，题目要求不能有重复的三元组，所以要注意跳过相同的值。

classSolution(object):defthreeSum(self,nums):""" :type nums: List[int] :rtype: List[List[int]] """n=len(nums)res=[]# 边界：长度不足3直接返回空ifn<3:returnres# 排序，双指针与去重的基础nums.sort()foriinrange(n):# 剪枝：第一个数已大于0，后续不可能凑出和为0ifnums[i]>0:break# 第一层去重：和前一个元素相同则跳过ifi>0andnums[i]==nums[i-1]:continue# 相向双指针初始化left,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal<0:# 和偏小，左指针右移增大数值left+=1eliftotal>0:# 和偏大，右指针左移减小数值right-=1else:# 找到合法解，加入结果集res.append([nums[i],nums[left],nums[right]])# 第二层：左指针去重，跳过连续相同值whileleft<rightandnums[left]==nums[left+1]:left+=1# 第三层：右指针去重，跳过连续相同值whileleft<rightandnums[right]==nums[right-1]:right-=1# 同步收缩指针，寻找下一组解left+=1right-=1returnres

需要注意第一层去重时必须和前一个元素比较(nums[i] == nums[i-1])，与后一位比较可能漏解，如[-1,-1,2]。如果遗漏二、三层去重，则可能生成完全相同的三元组。
该算法的时间复杂度为 O(n²)，主要包括三个部分：排序开销 O(nlog n)，外层遍历 O(n)，以及内层双指针遍历 O(n)，整体呈现平方级的增长趋势；空间复杂度为 O(log n)，仅包含排序所需的栈空间开销，结果存储不占用额外空间。

3.盛最多水的容器

盛最多水的容器是相向双指针 + 贪心思想的最典型代表。它无需数组排序，仅依靠问题本身的几何性质，就能通过双指针的定向移动将暴力 O (n²) 的复杂度压缩至 O (n)。
任意两条垂线构成的容器盛水量，由「两侧高度的较小值」和「两条线的水平间距」共同决定：

盛水量 = min (height [left], height [right] ) × ( right - left )

如果暴力枚举，两层循环枚举所有可能的左右边界组合，计算每一组的盛水量，遍历全程记录最大值，时间复杂度 O(n²)，数组长度较大时超时。

最优解法采用双向指针策略。初始时，左右指针分别置于数组两端以获得最大宽度。核心操作是每次移动高度较低的一侧的指针，其原理在于：

盛水量由较矮的板决定。若移动较高侧的指针，宽度必然缩小，而有效高度不会超过原短板的高度，导致面积无法增大；只有移动较矮侧的指针，才可能遇到更高的板，从而提升有效高度，获得更大的盛水量。

这一特性确保了我们可以安全地跳过所有"移动高板"的无意义组合。通过单次线性扫描即可找到最优解，且不会遗漏最大盛水量的情况。

classSolution(object):defmaxArea(self,height):""" :type height: List[int] :rtype: int """left=0right=len(height)-1max_area=0whileleft<right:# 计算当前容器的盛水量valid_height=min(height[left],height[right])width=right-left current_area=valid_height*width# 更新全局最大水量max_area=max(max_area,current_area)# 贪心决策：移动更矮的一侧指针ifheight[left]<height[right]:left+=1else:right-=1returnmax_area

这种算法时间复杂度为 O(n)，左右指针仅需遍历数组一次，每一步操作都能有效缩小搜索范围，避免重复访问；空间复杂度为 O(1)，仅使用固定数量的变量，无需额外存储空间，完全满足原地操作的条件。

4.接雨水

作为双指针专题的经典难题，接雨水是数组题型中的标杆之作。这道题目展现了从暴力解法到预处理优化，再到双指针极致压缩的完整优化路径，重点考察对问题本质的拆解能力和空间优化思维，是面试中高频出现的困难级考点。
本题的本质是逐位计算接水量再求和，对于任意位置 i，接水量由左右两侧最高柱子的「短板」决定：

位置 i 接水量 = max (0, min ( 左侧最高柱高度，右侧最高柱高度) - 当前柱高度 )

当差值为负时，说明当前柱子高于两侧挡板，无法承接雨水，接水量按 0 计算。
我们可以先通过暴力法理解题意，逐个遍历每个位置，分别向左右扫描找到两侧的最大柱子高度，代入核心公式计算当前位置接水量，累加得到总水量。

classSolution1(object):deftrap(self,height):n=len(height)res=0foriinrange(n):# 找左侧最高柱left_max=0forjinrange(i):left_max=max(left_max,height[j])# 找右侧最高柱right_max=0forjinrange(i+1,n):right_max=max(right_max,height[j])# 计算接水量water=min(left_max,right_max)-height[i]ifwater>0:res+=waterreturnres

暴力法时间复杂度为O(n²)，每个位置都需要向两侧完整扫描，数据量大时严重超时。
暴力法存在大量重复的最大值计算，我们可以提前用两个数组预处理出每个位置的左右侧最大值，消除重复遍历，将时间复杂度降为线性。

• left_max[i]：下标 i 左侧所有柱子的最大高度（不包含 i 本身）
• right_max[i]：下标 i右侧所有柱子的最大高度（不包含 i 本身）

classSolution(object):deftrap(self,height):n=len(height)ifn<3: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[i+1],height[i+1])res=0foriinrange(n):water=min(left_max[i],right_max[i])-height[i]ifwater>0:res+=waterreturnres

动态规划优化用三次线性遍历完成预处理与结果计算，将时间复杂度降到 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 """length=len(height)left,right=0,length-1l_max=r_max=0res=0whileleft<right:ifheight[left]<height[right]:ifheight[left]>l_max:l_max=height[left]else:res+=l_max-height[left]left+=1else:ifheight[right]>r_max:r_max=height[right]else:res+=r_max-height[right]right-=1returnres

指针从数组两端向中间靠拢，每一步都由更矮的一侧负责计算和移动；遇到更高的柱子就更新挡板高度，遇到低洼位置就计算该位置能承接的雨水量。全程仅遍历数组一次，指针相遇时计算结束，最终累加值即为总接水量。

三、总结

双指针是处理数组与链表问题的经典优化技巧，通过两个指针的协同遍历消除重复计算，能在 O(1) 额外空间内将暴力解法 O(n²) 的时间复杂度优化至 O(n)。主要分为两类：同向快慢指针和相向对撞指针，分别适用于原地修改和区间搜索场景。
本专题精选的四道题目全面展示了双指针的核心应用。移动零作为快慢指针入门题，演示了原地筛选与元素重排的基础思想盛最多水的容器、三数之和与接雨水则层层递进地展现了相向指针的进阶应用：从基于贪心的短板移动策略，到结合排序降维与去重的综合技巧，最终到极致空间优化的困难案例，完整呈现了双指针"利用单调性剪枝替代暴力枚举"的核心算法逻辑。