双指针

很经典

也很有意思

以后写…

283.移动零

解法:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slow = 0; //快慢双指针
        for(int fast = 0;fast < nums.size();fast++){
            if(nums[fast] != 0){
                nums[slow] = nums[fast];
                slow++;
            }
        }
        for(int j = slow;j < nums.size();j++){
            nums[j] = 0;
        }
    }
};

11.盛最多水的容器

解法:

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0,r = height.size() - 1;
        int ans = 0;

        while(l < r){
            int h = min(height[l], height[r]);
            int area = h * (r - l);
            ans = max(ans, area);

            if(height[l] < height[r]){
                l++;
            }else{
                r--;
            }
        }
        return ans;
    }
};

15.三数之和

解:

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        int n = nums.size();
        if(n < 3){
            return res;
        }
        sort(nums.begin(),nums.end());

        for(int i = 0; i < n - 2; i++){
            int l = i + 1;
            int r = n - 1;
            //i去重 思考...
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            while(l < r){
                int sum = nums[i] + nums[l] + nums[r];
                if(sum == 0){
                    res.push_back({nums[i],nums[l],nums[r]});
                    //l r去重 思索...
                    while(l < r && nums[l] == nums[l + 1]) l++;
                    while(l < r && nums[r] == nums[r - 1]) r--;
                    l++;
                    r--;
                }else if(sum < 0){
                    l++;
                }else{
                    r--;
                }
            }
        }
        return res;
    }
};

42.接雨水

解：

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int left = 0, right = n - 1;
        int leftmax = 0, rightmax = 0;
        int ans = 0;

        while(left < right){
            if(height[left] < height[right]){
                if(height[left] >= leftmax){
                    leftmax = height[left];
                }else{
                    ans += leftmax - height[left]; //思考...
                }
                left++;
            }else{
                if(height[right] >= rightmax){
                    rightmax = height[right];
                }else{
                    ans += rightmax - height[right]; //同理...
                }
                right--;
            }
        }
        return ans;
    }
};

思索…