leetcode.15 --- 三数之和

题目:

排序+双指针

首先想到的方法就是暴力解法，直接3层循环，肯定是不行的，


看了英雄哥的代码加的细节:可以先将答案数组先开好空间，如果数组个数小于3或者第一个数大于0，最后一个数小于0直接返回，如果第1个数和最后一个数都是0，则返回3个0.
代码如下:

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        int len = nums.size();
       //1.先排序
        sort(nums.begin(),nums.end());
        res.reserve(len > 256 ? 256 : len);
        if(len < 3 || nums[0] > 0 || nums[len-1] < 0) return res;
        if(!nums[0] && !nums[len-1])
        return {{0,0,0}};
        //开始遍历数组
        for(int i = 0;i < len;i++)
        {
            //如果第1个数就大于0，跳出循环
            if(nums[i] > 0) break;
            if(i > 0 && nums[i] == nums[i-1]) continue;//a去重
            int l = i + 1;
            int r = len - 1;
            while(l < r)
            {
                int sum = nums[i]+nums[l]+nums[r];
                if(sum == 0)
                {
                    //插入答案数组
                    res.push_back({nums[i],nums[l],nums[r]});
                    while(l < r && nums[r] == nums[r-1]) r--;//c去重
                    while(l < r && nums[l] == nums[l+1]) l++;//b去重
                    l++;
                    r--;
                }//sum > 0,右边的指针向左移动，相反则左指针向右移动
                 else if(sum > 0)  r--;
                 else   l++;
            }
        }
        return res;
    }
};
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
34
35
36
37
38