LeetCode 热题 100 | 双指针（上）

目录

1? 283. 移动零

2? 11. 盛最多水的容器

3? 15. 三数之和

---

菜鸟做题第一周，语言是 C++

1? 283. 移动零

解题思路：

1. 两个指针一前一后遍历数组
2. 前者永远指向 0，后者永远在寻找非 0 数的路上
3. 后者找到一个非 0 数就和前者进行一个数值交换

思路说明图：

• 上图并没有画出每一步，请自行脑补
• 由上图可见，i 始终指向 0，j 的作用就是寻找非 0 数
• 一旦找到就进行交换

思考过程：

本菜鸟一开始交换两数还用的是最传统的 temp 三步法，结果被 swap 函数一把子秒了！对于双指针，既然 i 和 j 必须是一前一后地移动（毕竟自己没有和自己交换的必要），那为什么初始化的时候要令 j 等于 i 呢？这是因为 nums 的长度可能为 1，你初始化 j = 1 就越界了。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int i = 0, j = 0;
        while (j < nums.size()) {
            if (nums[j] != 0) {
                swap(nums[i], nums[j]);
                ++i;
            }
            ++j;
        }
    }
};

每完成一次交换，i 就要向右移动一格，毕竟之前的序列已经处理好了。无论交不交换，j 都要向右移动一格。若交换，则代表 j 当前指向 0；若没交换，则还是代表 j 当前指向 0 。而 j 是用来寻找非 0 数的，因此必须向右移动。

2? 11. 盛最多水的容器

解题思路：

1. 两个指针一头一尾遍历数组
2. 若左侧更低则左边的指针移动，若右侧更低则右边的指针移动
3. 每次移动完就计算新的面积，并和历史最大面积做比较

思路说明图：

这里我们的移动标准是 “哪侧的边矮，我们就移动哪侧”。为什么这样做呢？难道不会遗漏更好的组合吗？举个例子，对于初始组合 1 和 9，面积的高度等于 1 这个矮边，又因为 9 离 1 最远，所以面积的宽度已经取到了极值，这就是针对 1 这个矮边的最大面积了！我们再怎么移动右侧的边也不能使面积增大。

同样地，当左侧的边移动到 2 时，9 成了矮边。在保证 9 是矮边的条件下，2 又是离 9 最远的，所以面积的宽度已经取到了极值，这就是针对 9 这个矮边的最大面积了！我们再怎么移动左侧的边也不能使面积增大。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int i = 0, j = height.size() - 1;
        int area = min(height[i], height[j]) * (j-i);
        while (i != j) {
            if (height[i] < height[j]) {
                ++i;
            } else if (height[i] > height[j]) {
                --j;
            } else {
                ++i;
            }
            area = max(area, min(height[i], height[j]) * (j-i));
        }
        return area;
    }
};

3? 15. 三数之和

解题思路：

1. 为数组排序
2. 进行三层循环，每层循环针对三数中的一个
3. 第二层和第三层体现了双指针，一个从头开始，一个从尾开始

思路说明图：

1）双指针

传统的三层循环如 method1 所示，即 i、j 和 k 都是从左至右遍历数组。但是因为排序后的数字是按从小到大的顺序排序的，并且要求 nums[i] + nums[j] + nums[k] == 0 。又由于 i 和 j 是从左至右遍历的，nums[i] + nums[j] 会变得越来越大，因此 nums[k] 应该越来越小！这就要求 k 从右至左进行遍历，如 method2 所示。

2）避免重复

if (i > 0 && nums[i] == nums[i - 1]) continue;

这行代码是为了避免三元组出现重复。如上图所示，我们只看第一层循环。

当 i 等于第一个 -4 的时候，j 和 k 屁颠屁颠地给 i 找满足要求的组合，它们考虑的数字包含 {-4, -1, -1, 0, 1, 2, 2} 。当 i 等于第二个 -4 的时候，j 和 k 还是屁颠屁颠地给 i 找满足要求的组合，它们考虑的数字包含 {-1, -1, 0, 1, 2, 2} 。

这里少考虑了一个 -4 会影响结果吗？答案是并不会。只能说为第二个 -4 找的三元组可能比为第一个 -4 找的少一个罢了（如果数组里还有个 8 的话，就会少一个 {-4, -4, 8}）但这并不影响啊，题目要求的就是不能重复！所以我们索性跳过第二个 -4，反正为它找的三元组已经存在了。

类似地，针对 j 也有这样的 if 语句。

if (j > i + 1 && nums[j] == nums[j - 1]) continue;

3）第三层循环

按理说，第三层循环也拿 for 做不就好了吗，条件为 j < k，只要 --k 就好了呀，但会超时……

还是那个思路 “能少循环就少循环”。

while (j < k && nums[i] + nums[j] + nums[k] > 0) --k;

这里有两个条件。一个是 j 不能遇上 k，它避免了 nums[k] 和 nums[i]、nums[j] 取到同一个位置的值；另一个是 nums[i] + nums[j] + nums[k] > 0，它避免了 nums[i] + nums[j] + nums[k] <= 0 以后，k 还在一个劲儿地往左移。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());

        // 第一层循环
        for (int i = 0; i < nums.size(); ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int k = nums.size() - 1;
            // 第二层循环
            for (int j = i + 1; j < nums.size(); ++j) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                // 第三层循环
                while (j < k && nums[i] + nums[j] + nums[k] > 0) --k;
                // 处理循环结果
                if (j == k) break;
                if (nums[i] + nums[j] + nums[k] == 0) {
                    result.push_back({nums[i], nums[j], nums[k]});
                }
            }
        }

        return result;
    }
};

这道题最离谱的是把 int k = nums.size() - 1; 改写到第二层循环里也会超时啊！？