相向双指针

167、两数之和 II - 输入有序数组

[两数之和 II - 输入有序数组][https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/]

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

暴力–两重循环

O(n^2)

利用有序

O(n)

利用两个变量（L， R）指向当前最小和最大的树，与目标数比较。如果大于，去掉最大的（L右移），小于，去掉最小的数（R左移）。

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

15、三数之和

[三数之和][https://leetcode.cn/problems/3sum/]

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

排序

O(n^2)

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        int n = nums.size();
        for(int i = 0; i < n - 2; ++ i){
            //如果重复，直接下一组
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            int x = nums[i];
            int l = i + 1;
            int r = n - 1;
            //最小组合都大于0，直接退出
            if(x + nums[i + 1] + nums[i + 2] > 0){
                break;
            }
            //当前最大组合都小于0，结束当前的循环
            if(x + nums[n - 1] + nums[n - 2] < 0){
                continue;
            }
            while(l < r){
                int num = x + nums[l] + nums[r];
                if(num < 0){
                    l ++;
                }else if(num > 0){
                    r --;
                }else{
                    ans.push_back({x, 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、盛最多水的容器

[盛最多水的容器][https://leetcode.cn/problems/container-with-most-water/]

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

相向双指针

O(n)

取两个指针指向两边，由于长度必定会缩短，所以如果想面积增大，则需要更矮的一边去寻找比它高的。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int l = 0;
        int r = n - 1;
        int area = 0;
        int ans = 0;
        while(l < r){
            area = min(height[l], height[r]) * (r - l);
            ans = max(area, ans);
            if(height[r] < height[l]){
                r --;
            }else{
                l ++;
            }
        }
        return ans;
    }
};

42、接雨水

[接雨水][https://leetcode.cn/problems/trapping-rain-water/]

[][]

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

前后缀分解

时间复杂度 O(n)

空间复杂度 O(n)

新建两个数组，第一个为前缀的最大高度，第二个为后缀最大高度，计算一个点的储水为，当前两个高度数组的较小值减去这个点的高度

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> pre_max(n, 0);
        vector<int> suf_max(n, 0);
        pre_max[0] = height[0];
        for(int i = 1; i < n; ++ i){
            pre_max[i] = max(pre_max[i - 1], height[i]);
        }
        suf_max[n - 1] = height[n -1];
        for(int i = n - 2; i >= 0; -- i){
            suf_max[i] = max(height[i], suf_max[i + 1]);
        }
        int ans = 0;
        for(int i = 0; i < n; ++ i){
            ans += (min(pre_max[i], suf_max[i]) - height[i]);
        }
        return ans;
    }
};

相向双指针

时间复杂度 O(n)

空间复杂度 O(1)

创建两个指针(L, R) ，两个变量分别存储前缀最大和后缀最大，由于最大值只会变大，不会减小，我们可以比较在左右元素的前缀最大和后缀最大。

对于左边的元素来说，如果前缀最大小于后缀最大，那么他的容积就已经可以确定，因为总是取小的那个，此时L就可以右移，并更新前缀最大。

对右边元素同理。

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int l = 0;
        int r = n - 1;
        int pre_max = height[0];
        int suf_max = height[r];
        int ans = 0;
        while(l < r){
            if(pre_max < suf_max){
                ans += min(pre_max, suf_max) - height[l];
                l ++;
                pre_max = max(height[l], pre_max);
            }else{
                ans += min(pre_max, suf_max) - height[r];
                r --;
                suf_max = max(height[r], suf_max);
            }
        }
        return ans;

    }
};