2. 双指针
约 2438 字大约 8 分钟
2025-08-30
2.1 移动零
- 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。示例 1：
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]示例 2：输入: nums = [0]
输出: [0]提示
思路：双指针的思路，慢指针初始指向 0 ，快指针遍历整个数组，遇到非 0 的数就用慢指针所在空间存储，同时慢指针+1，即指向下一个空位。
Pythonclass Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ i = 0 for j, num in enumerate(nums): if num: nums[i], nums[j] = nums[j], nums[i] i += 1C++class Solution { public: void moveZeroes(vector<int>& nums) { int i = 0; for (int &x : nums) { if (x) { swap(x, nums[i]); i++; } } } };
2.2 盛最多水的容器
- 给定一个长度为 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提示
思路：关键是理解短板效应。如示例一的图，我们在首尾各使用一个指针，计算初始容积，移动指针，如果容积变大，则更新。问题是怎么移动，移动哪条边？假如我们移动长的边，例如左边红色的线，首先让它变短（右移一位），容积必然变小，因为矩形的长宽都短了，然后如果变长呢？长变短宽不变（因为短板效应，容积和短的边有关），因此我们只能移动短的边。
重要
思考：为什么相等时移动左右两边都可以？首先，如果遇到左右相等的情况，那么里面都是比当前宽短的和只有一根比宽长的这两种情况，是可以直接 break 的，因为不可能比当前容积大，更不用说比从初始就记录的 res 大了，因此自然移动左右都可以。而只有当内部有两根以上长的情况，才会可能比当前容积大，既然有两根以上，那么先移动左还是右自然最终都会移到这两根内部最长的上面。
Pythonclass Solution: def maxArea(self, height: List[int]) -> int: left = res = 0 right = len(height) - 1 while left < right: area = (right - left) * min(height[left], height[right]) res = max(res, area) if height[left] < height[right]: left += 1 else: right -= 1 return resC++class Solution { public: int maxArea(vector<int>& height) { int left = 0, res = 0, right = height.size() - 1; while (left <right) { int area = (right - left) * min(height[left], height[right]); res = max(res, area); height[left] < height[right] ? left++ : right--; } return res; } };时间复杂度：O(n)。
空间复杂度：O(1)。
2.3 三数之和
- 给你一个整数数组 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遍历数组（优化：避免重复，遇到和上一个元素相同则跳过），j和k以首尾的方式来遍历i后面的部分，如果ijk大于0，那么k变小，如果ijk小于0，那么k变大，当ijk等于0时，就找到了，存储结果，jk同时中间移动一位，查找其他可能（优化：避免重复，遇到j和j-1、k和k+1相同则跳过）。
Pythonclass Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: nums.sort() # O(nlogn) res = [] n = len(nums) for i in range(n - 2): # O(n) if i > 0 and nums[i] == nums[i - 1]: # 优化：避免重复 continue if nums[i] + nums[i + 1] + nums[i + 2] > 0: # 优化：最小的三数大于0，则后续不可能等于0 break if nums[i] + nums[-2] + nums[-1] < 0: # 优化：当前和最大的两数小于0，则后续不可能等于0 continue j = i + 1 k = n - 1 while j < k: # O(n) if nums[i] + nums[j] + nums[k] > 0: k -= 1 elif nums[i] + nums[j] + nums[k] < 0: j += 1 else: res.append([nums[i], nums[j], nums[k]]) j += 1 while nums[j] == nums[j - 1] and j < k: # 优化：避免重复 j += 1 k -= 1 while nums[k] == nums[k + 1] and j < k: # 优化：避免重复 k -= 1 return resC++class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> res; ranges::sort(nums); int n = nums.size(); for (int i = 0; i < n - 2; i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break; if (nums[i] + nums[n - 1] + nums[n - 2] < 0) continue; int j = i + 1, k = n - 1; while (j < k) { if (nums[i] + nums[j] + nums[k] > 0) k--; else if (nums[i] + nums[j] + nums[k] < 0) j++; else { res.push_back({nums[i], nums[j], nums[k]}); for (j++; j < k && nums[j] == nums[j - 1]; j++); for (k--; j < k && nums[k] == nums[k + 1]; k--); } } } return res; } };时间复杂度：O(n2)。其中 n 为 nums 的长度。排序 O(nlogn)。外层循环枚举第一个数，就变成 167. 两数之和 II - 输入有序数组 了，做法是 O(n) 双指针。所以总的时间复杂度为 O(n2)。
空间复杂度：O(1)。
2.4 接雨水
- 给定 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提示
思路：考虑某一个位置能接多少水，取决于这个位置左边最大值和右边最大值，换种说法，可以把这个位置看成有一个木桶，木桶的左长度就是左边最大值，右长度就是右边的最大值，当前接水量为左长度和右长度的最小值减去柱子高度（短板效应）。因此很自然想到分别计算出前缀最大值和后缀最大值。
Pythonclass Solution: def trap(self, height: List[int]) -> int: n = len(height) res = 0 # 计算前缀最大值 pre_max = [0] * n pre_max[0] = height[0] for i in range(1, n): # O(n) pre_max[i] = max(pre_max[i-1], height[i]) # 计算后缀最大值 suf_max = [0] * n suf_max[-1] = height[-1] for i in range(n - 2, -1, -1): # O(n) suf_max[i] = max(suf_max[i+1], height[i]) # 计算每个位置的雨水 for i in range(n): # O(n) res += min(pre_max[i], suf_max[i]) - height[i] return resC++class Solution { public: int trap(vector<int>& height) { int n = height.size(); // 计算前缀最大值 vector<int> pre_max(n); pre_max[0] = height[0]; for (int i = 1; i < n; i++) { pre_max[i] = max(pre_max[i - 1], height[i]); } // 计算后缀最大值 vector<int> suf_max(n); suf_max[n - 1] = height[n - 1]; for (int j = n - 2; j >= 0; j--) { suf_max[j] = max(suf_max[j + 1], height[j]); } // 计算每个位置的雨水 int res = 0; for (int i = 0; i < n; i++) { res += min(suf_max[i], pre_max[i]) - height[i]; } return res; } };时间复杂度：O(n)。
空间复杂度：O(n)。
双指针的做法
优化空间复杂度：考虑现在只知道前几项的最大值和后几项的最大值，中间的状态不知道，但如果后几项中的最大值比前几项大，根据短板效应，即使中间状态还有更大的板子，装水的量也取决于短板，因此前几项的水量可以直接计算，反之亦然。注意 while 循环可以不加等号，因为在「谁小移动谁」的规则下，相遇的位置一定是最高的柱子，这个柱子是无法接水的。
Pythonclass Solution: def trap(self, height: List[int]) -> int: pre_max = suf_max = res = 0 left, right = 0, len(height) - 1 while left < right: # O(n) pre_max = max(pre_max, height[left]) suf_max = max(suf_max, height[right]) if pre_max < suf_max: res += pre_max - height[left] left += 1 else: res += suf_max - height[right] right -= 1 return resC++class Solution { public: int trap(vector<int>& height) { int pre_max = 0, suf_max = 0, res = 0; int left = 0, right = height.size() - 1; while (left < right) { pre_max = max(pre_max, height[left]); suf_max = max(suf_max, height[right]); res += pre_max < suf_max ? pre_max - height[left++] : suf_max - height[right--]; } return res; } };时间复杂度：O(n)。
空间复杂度：O(1)。