相向双指针

LCR 006. 两数之和 II - 输入有序数组

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while(l < r){
            int x = nums[l] + nums[r];
            if(x < target)l++;
            else if(x > target)r--;
            else{
                return {l,r};
            }
        }
        return {};
    }
};

15. 三数之和

代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int n = nums.size();
        vector<vector<int>> ans;
        for(int i = 0; i < n - 2; i++){//因为要给另外两个元素预留出空间，所以要< n - 2
            if(i && nums[i] == nums[i - 1])continue;//防止重复三元组
            if(nums[i] + nums[i + 1] + nums[i + 2] > 0)continue;
            if(nums[i] + nums[n - 1] + nums[n - 2] < 0)continue;
            int l = i + 1, r = n - 1;
            while(l < r){
                int x = nums[i] + nums[l] + nums[r];
                if(x < 0) l++;
                else if(x > 0) r--;
                else if(x == 0 && l < r){
                ans.push_back({nums[i],nums[l],nums[r]});     
                l++;
                while(l < r && nums[l] == nums[l - 1])l++;
                r--;
                while(l < r && nums[r] == nums[r + 1])r--;
                }
            }
        }
        return ans;
    }
};

11. 盛最多水的容器

代码

class Solution {
    //相向双指针
    //两个指针分列两边
    //每次均移动短板，移动长板结果不明，总移动短板可以增大
    //每轮移动短板不会导致最大值状态丢失
public:
    int maxArea(vector<int>& height) {
        int l = 0, r = height.size() - 1;
        int ans = 0;
        while(l < r){
            height[l] < height[r] ? ans = max(ans,(r - l) * height[l++]) : ans = max(ans,(r - l) * height[r--]) ;
        }    
        return ans;
    }
};

42. 接雨水

代码

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0, l = 0, r = height.size() - 1;
        int lmax = 0, rmax = 0;
        while(l < r){
            lmax = max(lmax,height[l]);
            rmax = max(rmax,height[r]);
            ans += lmax < rmax ? lmax - height[l++] : rmax - height[r--];
        }
        return ans;
    }
};