Day54 | 灵神 | 相向双指针：两数之和II-输入有序数组&&三数之和

两数之和 三数之和【基础算法精讲 01】_哔哩哔哩_bilibili

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

167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）

思路：

数组给咱们的是排序好的，那自然而然定义两根指针，一个在数组头l，一个在数组尾r

这样定义的好处是

两根指针中间的数字一定比头指针要大，一定比尾指针要小

如果两指针之和大于target的话，那中间某个数加上尾指针肯定也比target要大，那说明两个数加起来大了，那就把右边大的数字减小一点

如果两指针之和小于target的话，那头指针加上中间某个数肯定也比target要小，那说明两个数加起来小了，那就把左边大的数字增大一点

如果两指针之和等于target的话，那说明我们找到了答案直接返回就行

举例：

2 4 6 8 9 target=12

一开始 2 + 9=11小于12，那么不管是2和4,6,8哪个数字加都不可能达到12了，说明左边的选小了（同时也说明2肯定不会是答案了，就把2排除了，在4,6,8,9中选答案）

后来 4 + 9=13,大于12，那么不管是6,8哪个和9加都不可能比12小了，说明右边选大了（同时也说明9肯定不是答案了，就把9排除了，在4,6,8中选答案）

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int l=0,r=numbers.size()-1;
        while(l<r)
        {
            if(numbers[l]+numbers[r]>target)
                r--;
            else if(numbers[l]+numbers[r]<target)
                l++;
            else
                return {l+1,r+1};
        }
        return {l+1,r+1};
    }
};

一个分析时间复杂度的新角度：

为什么双指针能从暴力算法的O(n²)优化到O(n)呢？

我们可以试着量化得到的信息

暴力做法中，我们是拿着两个数字加起来和target比一比大小，我们花费了O(1)的时间，得到了O(1)的信息

而双指针做法中，我们利用单调性这个性质，只要这两个数加起来比target大，那我就知道数组中比两个数中较大的数大的那边全都不行，我们花费了O(1)的时间，却得到了O(n)的信息，所以我们可以从O(n²)优化到O(n)。

15.三数之和

15. 三数之和 - 力扣（LeetCode）

思路：

跟着上一题的思路走。上一次是nums[l]和nums[r]和target比大小

1
nums[l]+nums[r]=target

的时候我们就找到了答案，这一题只不过是转换为了

1
2
nums[l]+nums[r]-target = 0
nums[l]+nums[r]+nums[i] = 0

我们要找的就是

nums[i]在什么时候等于-target就行，在转换一下

其实就是找

1
nums[l]+nums[r]= -nums[i]

所以上一题是一个数组里面找到两个数加起来是一个固定的数target

这一题就一个数组里面找到两个数加起来是一个变化的数字nums[i]

那么只需要在上一题的代码上加一层循环，循环i就完事了

注意：不要忘记了排序，因为有序的情况下我们才用的双向双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size()-2;i++)
        {
            int l=i+1,r=nums.size()-1;
            while(l<r)
            {
                if(nums[l]+nums[r]+nums[i]>0)
                    r--;
                else if(nums[l]+nums[r]+nums[i]<0)
                    l++;
                else
                {
                    res.push_back({nums[i],nums[l],nums[r]});
                    l++;r--;
                }
            }
        }
        return res;
    }
};

这是跟着上一题的思路可以写到的地方

去重

1.对i去重

1
2
if(i&&nums[i]==nums[i-1])
	continue;

就是i在大于0时，如果和上一个i值一样的话那就直接跳过

2.对l和r进行优化

1
2
while(l<r&&nums[l]==nums[l-1]) l++;
while(l<r&&nums[r]==nums[r+1]) r--;

对l和r和 对i的操作是一样的

完整代码：

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
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size()-2;i++)
        {
            int l=i+1,r=nums.size()-1;
            if(i&&nums[i]==nums[i-1])
                continue;
            /*
            if (x + nums[i + 1] + nums[i + 2] > 0) break; // 优化一  前三个数字加起来都大于target了，就不用再算后面了
            if (x + nums[n - 2] + nums[n - 1] < 0) continue; // 优化二 第一个数和最后两个数加起来都小于0了，那后面的数也没必要遍历了，直接去遍历下一个i值
            */
            while(l<r)
            {
                if(nums[l]+nums[r]+nums[i]>0)
                    r--;
                else if(nums[l]+nums[r]+nums[i]<0)
                    l++;
                else
                {
                    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--;
                }

            }
        }
        return res;
    }
};