三数之和

15题三数之和

暴力解法（超出时间限制）

 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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        set<set<int>> s;
        int size = nums.size();
        for(int i = 1;i<size-1;i++){
            for(int j = 0;j<i;j++){
                for(int z = i+1;z<size;z++ ){
                    if(nums[i]+nums[j]+nums[z]==0){
                        set<int> set;
                        set.insert(nums[i]);
                        set.insert(nums[j]);
                        set.insert(nums[z]);
                        if(s.count(set)==0){
                            s.insert(set);
                            vector<int> tmp = {nums[i],nums[j],nums[z]};
                            ans.push_back(tmp);
                        }
                    }
                }
            }
        }
        return ans;
    }
};

暴力解法会超出时间限制，考虑跳过没有必要的循环检查，先进行排序，在原本暴力求解的基础上进行剪枝。

 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;
        set<set<int>> s;
        int size = nums.size();
        for(int i = 1;i<size-1;i++){
            for(int j = 0;j<i;j++){
                for(int z = i+1;z<size;z++ ){
                    int test = nums[i]+nums[j]+nums[z];
                    if(test==0){
                        set<int> set;
                        set.insert(nums[i]);
                        set.insert(nums[j]);
                        set.insert(nums[z]);
                        if(s.count(set)==0){
                            s.insert(set);
                            vector<int> tmp = {nums[i],nums[j],nums[z]};
                            ans.push_back(tmp);
                        }
                    }else if(test>0){
                        break;
                    }
                }
            }
        }
        return ans;
    }
};

上述解法不能正确的解决，使用双指针的解法进行求解

 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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 排序
        sort(nums.begin(),nums.end());
        vector<vector<int>> ans;
        set<set<int>> s;
        int size = nums.size();
        for(int i = 0;i<size&&nums[i]<=0;i++){
            int j = i+1,k = size-1;
            while(j<k){
                int n = nums[j]+nums[k]+nums[i];
                if(n<0){
                    j++;
                }else if(n>0){
                    k--;
                }else {
                    set<int> set;
                    set.insert(nums[i]);
                    set.insert(nums[j]);
                    set.insert(nums[k]);
                    if(s.count(set)==0){
                        s.insert(set);
                        vector<int> tmp = {nums[i],nums[j],nums[k]};
                        ans.push_back(tmp);
                    }
                    j++,k--;
                    // break;
                }
            }
        }
        return ans;
    }
};