Hexo

LeetCode-Hot100-双指针

  • ~2.53K 字
  1. 1. 283. 移动零 C++
  2. 2. 11. 盛最多水的容器 C++
  3. 3. 15. 三数之和 C++

283. 移动零 C++

原地栈，非零入栈，最后补0

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

11. 盛最多水的容器 C++

移动短边(java好像没有三目运算符？：)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxArea(vector<int>& height) {
        int ans = 0, left = 0, right = height.size() - 1;
        while (left < right) {
            int area = (right - left) *min(height[left], height[right]);
            ans = max(ans, area);
            // 如果 height[left] 更矮，则 height[left] 与右边的任意垂线都无法组成一个比 ans 更大的面积
            // 如果 height[right] 更矮，则 height[right] 与左边的任意垂线都无法组成一个比 ans 更大的面积
            height[left] < height[right] ? left++ : right--; 
        }
        return ans;
    }
};

15. 三数之和 C++

双指针，注意优化，去重。

题目要求答案中不能有重复的三元组。如何避免重复？

在外层循环中，如果发现 nums[i]=nums[i−1]，那么 nums[i] 与后面两个数组成的和为 0 的三元组，nums[i−1] 也能组成一模一样的三元组，这就重复了，所以遇到 nums[i]=nums[i−1] 的情况，直接 continue。

在内层循环中，当三数之和等于 0 时，为避免把相同的三元组计入答案，跳过后续相同的 nums[j] 和 nums[k]（也可以只跳过相同的 nums[j]）。

优化
优化一：如果 nums[i] 与后面最小的两个数相加 nums[i]+nums[i+1]+nums[i+2]>0，那么后面不可能存在三数之和等于 0，break 外层循环。

优化二：如果 nums[i] 与后面最大的两个数相加 nums[i]+nums[n−2]+nums[n−1]<0，那么内层循环不可能存在三数之和等于 0，但继续枚举，nums[i] 可以变大，所以后面还有机会找到三数之和等于 0，continue 外层循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        ranges::sort(nums);
        vector<vector<int>> ans;
        int n = nums.size();
        for (int i = 0; i < n - 2; i++) {
            int x = nums[i];
            if (i && x == nums[i - 1]) continue; //跳过重复数字
            if (x + nums[i + 1] + nums[i + 2] > 0) break; //优化1
            if (x + nums[n - 2] + nums[n - 1] < 0) continue; //优化2
            int j = i + 1, k = n - 1;
            while (j < k) {
                int s = x + nums[j] + nums[k];
                if (s > 0) k--;
                else if (s < 0) j++;
                else {
                    ans.push_back({x, nums[j], nums[k]});
                    for (j++; j < k && nums[j] == nums[j - 1]; j++); //跳过重复数字
                    for (k--; k > j && nums[k] == nums[k + 1]; k--); //跳过重复数字
                }
            }
        }
        return ans;
    }
};
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
, ,