图解 LeetCode Hot 100 中的双指针问题
283. 移动零
题目内容
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums =
[0,1,0,3,12]输出:
[1,3,12,0,0]
示例 2:
输入: nums =
[0]输出:
[0]
提示:
1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1
代码图解
class Solution: def moveZeroes(self, nums: List[int]) -> None: n = len(nums) i, j = 0, 0 while j < n: if nums[j] != 0: nums[i], nums[j] = nums[j], nums[i] i += 1 j += 1
11. 盛最多水的容器
题目内容
给定一个长度为 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
提示：
n == height.length2 <= n <= 1050 <= height[i] <= 104
代码图解
class Solution: def maxArea(self, height: List[int]) -> int: n = len(height) i, j = 0, n - 1 max_area = -1
while i < j: if height[i] > height[j]: max_area = max(max_area, (j - i) * height[j]) j -= 1 else: max_area = max(max_area, (j - i) * height[i]) i += 1
return max_area
15. 三数之和
题目内容
给你一个整数数组 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 。
提示：
3 <= nums.length <= 3000-105 <= nums[i] <= 105
代码图解
class Solution: def threeSum(self, nums: list[int]) -> list[list[int]]: ans = [] n = len(nums) nums.sort() for i in range(n - 2): if i > 0 and nums[i - 1] == nums[i]: # 同一个数在第一个位置只出现一次 continue
k = n - 1 for j in range(i + 1, n - 1): if j > i + 1 and nums[j - 1] == nums[j]: # 在第一个数确定的情况下，同一个数在第二个位置只出现一次 continue
while k > j and nums[i] + nums[j] + nums[k] > 0: k -= 1 if k > j and nums[i] + nums[j] + nums[k] == 0: ans.append([nums[i], nums[j], nums[k]]) if j >= k: break return ans
42. 接雨水
题目内容
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1:
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2:
输入：height = [4, 2, 0, 3, 2, 5]
输出：9
提示：
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
代码图解
class Solution: def trap(self, height: List[int]) -> int: n = len(height) l, r = 0, n - 1 lmax = rmax = 0 ans = 0 while l < r: lmax = max(lmax, height[l]) rmax = max(rmax, height[r]) if lmax < rmax: ans += lmax - height[l] l += 1 else: ans += rmax - height[r] r -= 1 return ans一个位置能接多少雨水取决于左侧的最大值和右侧的最大值，所以在左右双指针向中间移动的过程中记录左侧出现过的最大值和右侧出现过的最大值。
每次迭代，如果左侧出现的最大值更小，那么左端点能接到的水是确定的，同时移动左侧的指针，l += 1；
如果右侧出现的最大值更小，那么右端点能接到的水是确定的，同时移动右侧的指针 r -= 1。
支持与分享
如果这篇文章对你有帮助，欢迎分享给更多人或赞助支持！