Problem

leetcode链接problem

Code

先上我的这超时的破代码，思想是把情况分成了3种，正正负，正负负，正负零，以及000的特例。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        vector<vector<int>> result0 = {};
        vector<int> positive;
        vector<int> negitive;
        vector<int> zero;
        
        if(nums.size() <= 2)
        {
            return result0;
        }

        //sort(nums.begin(), nums.end());
        for(vector<int>::iterator it=nums.begin();it!=nums.end();it++)
        {
            if(*it > 0){
                positive.push_back(*it);
            }
            else if(*it < 0){
                negitive.push_back(*it);
            }
            else{
                zero.push_back(*it);
            }
        }
        sort(positive.begin(), positive.end());
        sort(negitive.begin(), negitive.end());

        if(zero.size() >= 3){
            vector<int> temp = {0,0,0};
            result.push_back(temp);
        }

        for(int i=0;i<positive.size();i++)
        {
            for(int j=0;j<negitive.size();j++){
                for(int k=0;k<zero.size();k++){
                    if(positive[i] + negitive[j] + zero[k] == 0){
                        vector<int> temp = {positive[i],negitive[j],zero[k]};
                        int label = 0;
                        if(result.size() > 0){
                            for(int z=0;z<=result.size()-1;z++){
                                if(temp == result[z]) label = 1;

                            }
                            if(!label)
                            {
                                result.push_back(temp);
                            }

                        }
                        else{
                            result.push_back(temp);
                        }

                    }
                }
            }
        }

        for(int i=0;i<positive.size();i++)
        {
            for(int j=0;j<negitive.size();j++){
                for(int k=0;k<negitive.size();k++){
                    if(j == k)
                    {
                        break;
                    }
                    if(positive[i] + negitive[j] + negitive[k] == 0){

                        vector<int> temp = {positive[i],negitive[j],negitive[k]};
                        int label = 0;
                        if(result.size() > 0){
                            for(int z=0;z<=result.size()-1;z++){
                                if(temp == result[z]) label = 1;

                            }
                            if(!label)
                            {
                                result.push_back(temp);
                            }

                        }
                        else{
                            result.push_back(temp);
                        }
                    }
                }
            }
        }
        for(int i=0;i<positive.size();i++)
        {
            for(int j=0;j<negitive.size();j++){
                for(int k=0;k<positive.size();k++){
                    if(i == k)
                    {
                        break;
                    }
                    if(positive[i] + negitive[j] + positive[k] == 0){
                        vector<int> temp = {positive[i],negitive[j],positive[k]};
                        int label = 0;
                        if(result.size() > 0){
                            for(int z=0;z<=result.size()-1;z++){
                                if(temp == result[z]) label = 1;

                            }
                            if(!label)
                            {
                                result.push_back(temp);
                            }

                        }
                        else{
                            result.push_back(temp);
                        }
                    }
                }
            }
        }

        return result;
    }
};

倒数第三个样例超时了，设计上确实有问题，里面包含了很大部分的重复计算。故网上找答案。
其实我总觉得我这个写法比直接三次循环还要low，感觉有点复杂，关键问题是，还要处理掉重复的情况。
一下答案室友倒是昨天跟我提了一句。降维度，先算两个数，然后在加第三个数。
一下算法就设计的很好，其实跟11题的水桶问题有点相似，就是排序以后从两边推进。

class Solution{
public:
    vector< vector<int> > threeSum(vector<int> &num) {
        vector<int> numSet(3);
        vector< vector<int> > r;
        // 1.排序
        sort(num.begin(), num.end());
        int sum;
        int len = num.size();
        // 2.拿出第一个数，转化为两数和问题。注意外层循环到倒数第三个数即可
        for(int i = 0; i < len-2; i++) {
            sum = 0 - num[i];
            numSet[0] = num[i];
            // 3.两数和问题
            for(int j = i+1, k = len-1; j < k;) {
                if(num[j] + num[k] == sum) {
                    numSet[1] = num[j++];
                    numSet[2] = num[k--];
                    r.push_back(numSet);
                    // 根据题目要求，跳过重复元素
                    while(j < k && num[j] == num[j-1]) 
                        j++;
                    while(j < k && num[k] == num[k+1])
                        k--;
                }
                else if(num[j] + num[k] < sum)
                    j++;
                else 
                    k--;
            }
            while(i < len-2 && num[i+1] == num[i])
                i++;
        }
        return r;
    }
};