力扣 hot100 - 双指针

868 words

4 minutes

力扣 hot100 - 双指针

2026-03-12

hot100

283. 移动零#

开一个指针寻找并定位到当前最左边 $0$ 的位置，另一个指针向后找，遇到第一个非 $0$ 的数字后，两个指针位置的数字进行交换，同时第一个指针继续寻找并定位到当前最左边 $0$ 的位置，以此类推，像冒泡一样把非 $0$ 的数字冒到左边来。

代码：

1
class Solution {
2
public:
3
    void moveZeroes(vector<int>& nums) {
4
        int zero = 0;
5
        for (int i = 0; i < nums.size(); i++) {
6
            if (nums[i]) {
7
                swap(nums[zero], nums[i]);
8
                zero++;
9
            }
10
        }
11
    }
12
};

11. 盛最多水的容器#

考虑左右指针一开始分别指向左右两端，逐渐向中间合并，考虑左右指针指向的线的高度，若较高一方向指针另一方移动，无论如何盛水体积都不会比现在更多，所以每次记录容器容积后，选较矮一方的指针向另一方移动，两边互相逼近即可。

代码：

1
class Solution {
2
public:
3
    int maxArea(vector<int>& height) {
4
        int l = 0, r = height.size() - 1, ans = 0;;
5
        while (l < r) {
6
            ans = max(ans, (r - l) * min(height[l], height[r]));
7
            height[l] < height[r] ? l++ : r--;
8
        }
9
        return ans;
10
    }
11
};

15. 三数之和#

看数据范围可以在 $O(n^2)$ 的复杂度内解决问题。

所以我们先花 $O(n)$ 枚举数组内的每一个数 $nums_i$ ，这样就可以把问题简化成在数组的其他数里找出两个跟他的和是 $0$ 的两个数。那怎么用剩下的 $O(n)$ 完成找两个数的操作呢。

考虑排序和双指针，我们将数组排序后取两个指针 $l$ 和 $r$ 分别指向 $nums_i$ 的下一个数字和数组最后一个数字，这时候我们可以发现：

nums_i+nums_l+nums_r\leq nums_i+nums_{l+1}+nums_r

和

nums_i+nums_l+nums_r\leq nums_i+nums_l+nums_{r-1}

这样我们令 $sum=nums_i+nums_l+nums_r$ ，如果 $sum < 0$ ，则让 $l+1$ ，如果 $sum > 0$ ，则让 $r-1$ 。直到 $sum=0$ ，这时我们跳过 $l$ 后面和他相同的所有数和 $r$ 前面和他相同的所有数，保证不重复即可。

代码：

1
class Solution {
2
public:
3
    vector<vector<int>> threeSum(vector<int>& nums) {
4
        int n = nums.size();
5
        ranges::sort(nums);
6
        vector<vector<int>> ans;
7
        for (int i = 0; i < n; i++) {
8
            if (i != 0 && nums[i] == nums[i - 1]) continue;
9
            int l = i + 1, r = n - 1;
10
            while (l < r) {
11
                int sum = nums[i] + nums[l] + nums[r];
12
                if (sum < 0) l++;
13
                else if (sum > 0) r--;
14
                else {
15
                    ans.push_back({nums[i], nums[l], nums[r]});
16
                    l++, r--;
17
                    while (l < r && nums[l - 1] == nums[l]) l++;
18
                    while (l < r && nums[r + 1] == nums[r]) r--;
19
                }
20
            }
21
        }
22
        return ans;
23
    }
24
};

42. 接雨水#

每个位置能存多少水取决于该位置左侧和右侧最高的柱子中较矮的那个，我们令位置 $i$ 左侧最高的柱子高度为 $l\_max_i$ ，右侧最高的柱子高度为 $r\_max_i$ ，那么位置 $i$ 能存的水的量为：

\text{min}(l\_max_i,r\_max_i)-height_i

朴素做法是,对每个位置都往左、往右找最高柱子，再计算答案，但这样时间复杂度是 $O(n^2)$ 。更好的做法是用双指针 $l$ 和 $r$ 从两侧往中间夹，同时维护左右两侧最高的柱子 $lm$ 和 $rm$ 。

如果 $lm<rm$ 则此时 $l$ 位置的存水量就可以决定了，反之则 $r$ 位置的存水量可以确定，累加到答案里之后向中间逼近即可。

1
class Solution {
2
public:
3
    int trap(vector<int>& height) {
4
        int l = 0, r = height.size() - 1, lm = 0, rm = 0, ans = 0;
5
        while (l < r) {
6
            lm = max(lm, height[l]);
7
            rm = max(rm, height[r]);
8
            ans += lm < rm ? lm - height[l++] : rm - height[r--];
9
        }
10
        return ans;
11
    }
12
};