LeetCode Hot100 双指针

Posted on Edited on

移动零

Problem

https://leetcode.cn/problems/move-zeroes/description/?envType=study-plan-v2&envId=top-100-liked

Solution

设置一个指针指向遇到非0数后该数应该放置的位置，遍历数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int zeroStart = 0;

        for (int i = 0; i < nums.size(); i ++)
        {
            if (nums[i] != 0)
            {
                swap(nums[zeroStart++], nums[i]);
            }
        }
    }
};

盛水最多的容器

Problem

https://leetcode.cn/problems/container-with-most-water/?envType=study-plan-v2&envId=top-100-liked

Solution

l, r双指针，每次移动较小的那边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int l = 0, r = n-1;
        int ans = 0;
        while (l < r)
        {
            ans = max(ans, min(height[l], height[r]) * (r-l));
            if (height[l] < height[r])
            {
                l ++;
            }
            else
            {
                r --;
            }
        }
        return ans;
    }
};

三数之和

Problem

https://leetcode.cn/problems/3sum/?envType=study-plan-v2&envId=top-100-liked

Solution

将数组从小到大排序，由于数组升序，i从前往后枚举，双指针j，k分别从0，n-1开始遍历，寻找符合要求的数。

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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for (int i = 0; i < n-2; i ++)
        {
            if (i != 0 && nums[i] == nums[i-1]) continue;
            int k = n - 1;
            for (int j = i + 1; j < n - 1 && k > j; j ++)
            {
                if (j != i + 1 && nums[j] == nums[j-1]) continue;

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

                if (k > j && nums[i] + nums[j] + nums[k] == 0)
                {
                    ans.push_back({nums[i], nums[j], nums[k]});
                }
            }
        }
        return ans;
    }
};

接雨水

Problem

https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-100-liked

Solution

从左往右遍历，记录当前位置左边的最大值，从右往左遍历，记录当前位置右边的最大值。当前位置最多可以接max(min(left_max[i], right_max[i]) - height[i], 0)的水。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> left_max(n, 0);
        for (int i = 1; i < n; i ++)
        {
            left_max[i] = max(left_max[i-1], height[i-1]);
        }
        vector<int> right_max(n, 0);
        for (int i = n-2; i >= 0; i --)
        {
            right_max[i] = max(right_max[i+1], height[i+1]);
        }

        int ans = 0;
        for (int i = 0; i < n; i ++)
        {
            ans += max(min(left_max[i], right_max[i]) - height[i], 0);
        }
        return ans;
    }
};