LeetCode-hot100——双指针

什么情况下可以用双指针方法

1. 数据特征（必要条件）

• 数据结构是有序的数组 / 字符串（最核心特征）：左右指针的核心是 “通过指针移动调整值的大小 / 满足匹配条件”，有序性是指针移动有明确方向的前提；
• 数据结构是线性的、可通过下标 / 索引访问两端（数组、字符串、双链表）：左右指针需要从 “两端向中间” 移动，无法访问两端的结构（如单链表）不适合。

2. 问题目标（充分条件）

问题要求在数据中找「一对 / 一组元素」满足以下特征之一：

• 数值类：两数 / 三数之和、目标差值、最接近目标值；
• 匹配类：回文验证、对称判断、字符匹配；
• 操作类：反转数组 / 字符串、移除指定元素（有序场景）、分区（如快速排序的 partition）。

不适用情况

1. 数据无序且无法排序

比如 “两数之和（无序数组）”：

• 若题目要求返回原始下标，排序会打乱下标，此时无法用左右指针（只能用哈希表）；
• 核心原因：排序破坏了问题的约束条件，左右指针的有序前提消失。

2. 数据结构无法访问两端

比如 “单链表的回文验证”：

• 单链表只能从头部遍历，无法直接访问尾部，无法初始化右指针；
• 替代方案：先用快慢指针找中点，再反转后半段链表，再用双指针比较（但已不是纯左右指针）。

3. 问题目标是 “全局遍历” 而非 “两端匹配”

比如 “数组中找最长递增子序列”：

• 问题目标是找递增序列，无 “两端向中间” 的匹配逻辑，左右指针无移动方向；
• 核心原因：问题不依赖 “两端值的比较”，无法通过指针移动缩小问题范围。

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]

示例 2:

输入: nums = [0] 输出: [0]

思路：

• 让左右指针从起点开始，当右指针遇到非零数时，两个指针的值交换
• 左指针的左边都是非零数
• 右指针的左边至左指针都为零

class Solution: def moveZeroes(self, nums: List[int]) -> None: n = len(nums) left = right = 0 while right < n: if nums[right] != 0: nums[left], nums[right] = nums[right], nums[left] left += 1 right += 1 return nums 

盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1] 输出：1

思路：

• 让左右指针从两端开始，"谁短谁移动"
• 定义一个最大面积MAX_area，每移动一次就与当前面积比较，将较大面积的值存放在MAX_area中。

class Solution: def maxArea(self, height: List[int]) -> int: max_area = 0 left= 0 right= len(height) - 1 while left < right: width=right-left h=min(height[left],height[right]) area=h*width max_area=max(max_area,area) if height[left]>height[right]: right-=1 else: left+=1 return max_area 

三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。

思路：

• 因为是三数相加，如果用暴力的方法会超出时间限制
• 先给数组排序，让i从头开始，左指针从i后一位，右指针从右端开始遍历
• 三数之和大于0，则让右指针移动；小于0，则让左指针移动
• 注意：遍历前要确保不出现相同元素的三元组，所以需要判断前后元素是否一致，避免重复遍历。

class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: result = [] nums.sort() for i in range(len(nums)): if nums[i]>0: break if i>0 and nums[i]==nums[i-1]: continue left=i+1 right=len(nums)-1 while left<right: current_num=nums[i]+nums[left]+nums[right] if current_num==0: result.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 current_num<0: left+=1 else: right-=1 return result