2. 双指针

约 2438 字大约 8 分钟

2025-08-30

2.1 移动零

283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意，必须在不复制数组的情况下原地对数组进行操作。

示例 1：

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

示例 2：

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

提示

思路：双指针的思路，慢指针初始指向 0 ，快指针遍历整个数组，遇到非 0 的数就用慢指针所在空间存储，同时慢指针+1，即指向下一个空位。

Python

class 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 += 1

C++

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int i = 0;
        for (int &x : nums) {
            if (x) {
                swap(x, nums[i]);
                i++;
            }
        }
    }
};

2.2 盛最多水的容器

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
提示
思路：关键是理解短板效应。如示例一的图，我们在首尾各使用一个指针，计算初始容积，移动指针，如果容积变大，则更新。问题是怎么移动，移动哪条边？假如我们移动长的边，例如左边红色的线，首先让它变短（右移一位），容积必然变小，因为矩形的长宽都短了，然后如果变长呢？长变短宽不变（因为短板效应，容积和短的边有关），因此我们只能移动短的边。
重要
思考：为什么相等时移动左右两边都可以？首先，如果遇到左右相等的情况，那么里面都是比当前宽短的和只有一根比宽长的这两种情况，是可以直接 break 的，因为不可能比当前容积大，更不用说比从初始就记录的 res 大了，因此自然移动左右都可以。而只有当内部有两根以上长的情况，才会可能比当前容积大，既然有两根以上，那么先移动左还是右自然最终都会移到这两根内部最长的上面。
Python
```
class 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 res
```
C++
```
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 三数之和

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 。

提示

思路：要充分利用已经排好序的信息，面多加水水多加面。用一个指针i遍历数组（优化：避免重复，遇到和上一个元素相同则跳过），j和k以首尾的方式来遍历i后面的部分，如果ijk大于0，那么k变小，如果ijk小于0，那么k变大，当ijk等于0时，就找到了，存储结果，jk同时中间移动一位，查找其他可能（优化：避免重复，遇到j和j-1、k和k+1相同则跳过）。

Python

class 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 res

C++

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(n^2)$ 。其中 n 为 nums 的长度。排序 $O(nlogn)$ 。外层循环枚举第一个数，就变成 167. 两数之和 II - 输入有序数组了，做法是 $O(n)$ 双指针。所以总的时间复杂度为 $O(n^2)$ 。

空间复杂度： $O(1)$ 。

2.4 接雨水

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

提示

思路：考虑某一个位置能接多少水，取决于这个位置左边最大值和右边最大值，换种说法，可以把这个位置看成有一个木桶，木桶的左长度就是左边最大值，右长度就是右边的最大值，当前接水量为左长度和右长度的最小值减去柱子高度（短板效应）。因此很自然想到分别计算出前缀最大值和后缀最大值。

Python

class 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 res

C++

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 循环可以不加等号，因为在「谁小移动谁」的规则下，相遇的位置一定是最高的柱子，这个柱子是无法接水的。

Python

class 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 res

C++

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)$ 。