LeetCode热题100刷题2：283. 移动零、11. 盛最多水的容器、15. 三数之和、42. 接雨水

283. 移动零

挺简单的没啥说的

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        //快慢指针  
        // 快指针负责往前遍历，慢指针记录快指针遍历过的把0撵走的最后一个元素的位置
        // 然后快指针遍历完之后，慢指针到结尾直接赋0就行
        int j=0;
        for(int i=0;i<nums.size();i++) {
            if(nums[i]!=0) {
                nums[j]=nums[i];
                j++;
            }
            else {
                continue;
            }
        }
        for(int i = j;i<nums.size();i++) {
            nums[i]=0;
        }
    }
};

11. 盛最多水的容器

双指针，主要是控制i和j的移动逻辑：左边高度低i++，右边高度低j–

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

15. 三数之和

**三个数改为两个数的双指针：外层逐个遍历负值nums[i]，内层用双指针控制和为-nums[i]
注意不重复这个限制条件①外层循环的nums[i]不重复②内层nums[j] 和 nums[k]也不重复
**

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        if(nums.size()<3)
            return res;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++) {
            if(nums[i] > 0) {
                return res;
            }
            if(i>0 && nums[i]==nums[i-1])
                continue;
            
            int j = i+1;
            int k = nums.size()-1;
            while(j<k) {
                if(nums[j]+nums[k] > -nums[i])
                    k--;
                else if(nums[j]+nums[k] < -nums[i])
                    j++;
                else if(nums[j] + nums[k] == -nums[i])
                {
                    res.push_back(vector<int>{nums[i],nums[j],nums[k]});
                    j++;
                    k--;
                    //这里的判断条件 附加了 j<k，要满足这个外层while循环的前提条件
                    while(j<k && nums[j]==nums[j-1])
                        j++;
                    while(j<k && nums[k]==nums[k+1])
                        k--;
                }
            }
        }
        return res;
    }
};

42. 接雨水

双指针，以左侧最大值left_max为基准计算当前左侧指针柱子的落差，以右侧最大值right_max为基准计算当前右侧指针柱子的落差：然后ans +=
left_max - height[left]
right_max-height[right]
每次计算的时候加上前面已经计算过的雨水；
最后注意控制左右侧指针的移动

在这里插入图片描述

class Solution {
public:
    //双指针做法 秒呀~
    // left, l_max  right, r_max
    int trap(vector<int>& height) {
        if(height.size()<=1)
            return 0;
        int l=0;
        int l_max=height[l];
        int r=height.size()-1;
        int r_max = height[r];
        int ans = 0;
        while(l<r) {
            l_max = max(l_max,height[l]);
            r_max = max(r_max,height[r]);
            if(height[l] < height[r]) {
                
                ans = ans+(l_max - height[l]);
                l++;
            }
            else if(height[r] <= height[l]) {
                ans = ans+(r_max-height[r]);
                r--;
            }
        }
        return ans;

    }
};