Leetcode12

两数之和&三数之和

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        int left = 0, right = numbers.size() - 1;
        for (;;) { // left < right
            int s = numbers[left] + numbers[right];
            if (s == target) return {left + 1, right + 1};
            s > target ? --right : ++left;
        }
    }
};

总结

若是暴力做法，直接是n方的复杂度，但是需要用上有序列表的条件；

例如 2 3 4 8 9 一开始选择2 9 若是得到6，那么11大于6，9已经是最大的了，若还是2右移为3，那么更加大了，只有9左移；同理，若是比target小的时候，左边的数小，右移动；

这是关键思想，之后三数之和也是这个思路；

灵神的题解更简洁，其中这道题保证唯一有解，所以一开始进入一个无限循环；

用三目运算更方便；

错解

 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<int> twoSum(vector<int>& numbers, int target) {
        int n=numbers.size();
        int left=0,right=n-1;
        vector<int> res;
        while(left<right){
            if(numbers[left]+numbers[right]>target)
                right--;
            else if(numbers[left]+numbers[right]<target)
                left++;
            else{
                res.emplace_back(left+1);
                res.emplace_back(right+1);
            // break;
                        return res;

            }
                
        }   
                        // return res;
//  return {left + 1, right + 1};
    }
};

错因在于对于循环控制条件没有写好，编译器认为你没有考虑完所有情况；这时要么别用这种if elseif结构；要么对其中进行break，可以解决报错；

修改后

 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 n=numbers.size();
        int left=0,right=n-1;
        while(left<right){
            if(numbers[left]+numbers[right]>target)
                right--;
            else if(numbers[left]+numbers[right]<target)
                left++;
            else
                break;                
        }   
        return {left + 1, right + 1};
    }
};

其中vector可以写成这样也需要注意；

15.三数之和:fire::fire:

 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


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) {
            int x = nums[i];
            if (i && x == nums[i - 1]) continue; // 跳过重复数字
            if (x + nums[i + 1] + nums[i + 2] > 0) break; // 优化一
            if (x + nums[n - 2] + nums[n - 1] < 0) continue; // 优化二
            int j = i + 1, k = n - 1;
            while (j < k) {
                int s = x + nums[j] + nums[k];
                if (s > 0) --k;
                else if (s < 0) ++j;
                else {
                    ans.push_back({x, nums[j], nums[k]});
                    j++;//形如 2 3 4 5 已经有了2 5 再找 3 4
                    while(j<k&&nums[j] == nums[j - 1])
                        ++j;
                    k--;
                    while(j<k&&nums[k] == nums[k + 1])
                        --k;                        
                    
                }
            }
        }
        return ans;
    }
};

总结

其实就是先定下来i，然后在i的基础上做j与k的两数之和；

最后要考虑清晰关于重复数字的情况，一步步来考虑，别一开始就考虑重复数字的情形；

此处好几个难点

        if (x + nums[i + 1] + nums[i + 2] > 0) break; // 优化一
        if (x + nums[n - 2] + nums[n - 1] < 0) continue; // 优化二

优化2处不可以用break，因为优化1处，当前i 与它之后的两个必定是此时所有数最小的了，之后没有比他更小的了，break；

但是当前i加上数组末尾的两个数确实不是当前最大的，因为i不一定是倒数第三；这个前往小心

附录

参考文献

版权信息

本文原载于[Alvarez’s Blog](Alvarez’s Blog (akihi878.github.io))，遵循CC BY-NC-SA 4.0协议，复制请保留原文出处。