LeetCode 热题 100 | 双指针(上)

发布时间:2024年01月18日

目录

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; 改写到第二层循环里也会超时啊!?

文章来源:https://blog.csdn.net/m0_64140451/article/details/135680828
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。