3Sum——解題報告

    【題目】

     Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)

The solution set must not contain duplicate triplets.

For example, given array S = {-1 0 1 2 -1 -4},

A solution set is:

(-1, 0, 1)

(-1, -1, 2)

    【分析】

    我們做過這樣的題目，給定一個數組和一個target，找出數組中的a+b = target。那麼這道題目變成了a，b，c三個數。

    其實，我們周遊每個a，然後target' = targer - a. 也就變成了找出b+c = target'。和上面的題目一樣吧~

    【代碼】

    上述解法的時間複雜度最快也隻能達到O(n^2)。

    需要解釋的是，下面給出的代碼在LeetCode送出的時候，一直是LTE。線下測試時對的，查找了答案之後發現，主體思路一樣，隻不過我用到的是set去重，可能這部分比較耗時。。。

vector< vector<int> > threeSum(vector<int>& nums) 
{
    //if(nums.empty())
        //return;
        
    sort(nums.begin(), nums.end());
    set< vector<int> > res1; 
    set< vector<int> >::iterator iter;
    vector< vector<int> > res2;
	vector<int> tmp;
    
    if(nums.size() < 3)
        return res2;
        
    for(int i = 0; i < nums.size() - 2; i++)
    {
        int current = nums[i]; 
        int diff = 0 - current; // the target
        
        int head = i + 1, tail = nums.size() - 1;
        while(head < tail)
        {
            if(head == i)  // skip the current
                {head++; continue;}
            if(tail == i)
                {tail--; continue;}
            
            if(nums[head] + nums[tail] == diff)
            {
				//cout<<i<<' '<<head<<' '<<tail<<endl;
                tmp.push_back(current); tmp.push_back(nums[head]); tmp.push_back(nums[tail]);
                sort(tmp.begin(), tmp.end());  // sort
				//cout<<tmp[0]<<' '<<tmp[1]<<' '<<tmp[2]<<endl;
				//cout<<current<<' '<<nums[head]<<' '<<nums[tail]<<endl;
                res1.insert(tmp);  // insert into the set
				tmp.clear();
                head++;
                tail--;
                continue;
            }
            else if(nums[head] + nums[tail] < diff)
            {
                head++;
                continue;
            }
            else
            {
                tail--;
                continue;
            }
        }
    }
    
    for(iter = res1.begin(); iter != res1.end(); ++iter)
        res2.push_back(*iter);
    
    return res2;
}
           

下面給出一個ac的參考答案：

http://bbs.csdn.net/topics/390931100