leetcode問題解|3 Sum問題

problem:

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)

3つの和が0の数を見つけて、順番に出力して、そして繰り返しの組み合わせを取り除きます
thinking:
(1)直感的にソートして検索するほうが簡単だと教えてくれました.
(2)双数求和は二分検索(双ポインタ)を採用でき、時間の複雑さはO(nlogn)に制御でき、三数求和にも広がる!!!
しかし、具体的に実現したとき、私はカーブを曲がって、時間の複雑さが最悪0に達した(n*n)
まず優秀な実現を見てみると、確かに細かく簡潔で、細かく味わうことができます.

class Solution {
public:

    //    
void InsertSort(vector<int> &a, int n)
{
	int temp;
	for (int i = 1; i < n; ++i)
	{
		temp = a[i];
		int j;
		for (j = i; j > 0 && temp < a[j - 1]; --j)
		{
			a[j] = a[j - 1];
		}
		a[j] = temp;
	}
}

     vector<vector<int> > threeSum(vector<int> &num) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        
        vector<vector<int>> res;

		if (num.size() < 3)  //  3  
			return res;

		//       （  ）  
		InsertSort(num,num.size()); 
        
        for (int i = 0; i < num.size(); ++i)
        {
			//  
            if (i != 0 && num[i] == num[i-1])
				continue;

            int p = i + 1, q = num.size() - 1;
            int sum = 0;
            
			//      2， 3  
            while (p < q)
            {
                sum = num[i] + num[p] + num[q];
                
                if (sum == 0)
                {
                    vector<int> newRes;
                    newRes.push_back(num[i]);
                    newRes.push_back(num[p]);
                    newRes.push_back(num[q]);
					InsertSort(newRes,newRes.size());
                    res.push_back(newRes);

			
					//       2  ，    
					while (++p < q  && num[p-1] == num[p])
					{
						//do nothing
					}
					while (--q > p && num[q+1] == num[q])
					{
						//do noghing
					}
                }
                else if (sum < 0)  //   ，p    
				{
                    ++p;
				}
                else            //   ，q    
				{
                    --q;
				}
            }
        }
        
        return res;
    }
};

最後に自分のバージョンを貼って、現地の実測に合格しました.

void find(int i, int &p, int j,vector<int> tmp, vector<vector<int> > &result)
{
    cout<<"i "<<i<<"p "<<p<<"j"<<j<<endl;
    cout<<tmp.at(i)<<"_"<<tmp.at(p)<<"_"<<tmp.at(j)<<endl;
    int index=0xff;
    while((index!=0x00)&&(p!=i)&&(p!=j))
    {
        if(tmp.at(i)+tmp.at(p)+tmp.at(j)>0)
        {
            p--;
            index&=0x0f;
        }
        else if(tmp.at(i)+tmp.at(p)+tmp.at(j)<0)
        {
            p++;
            index&=0xf0;
        }
        else if(tmp.at(i)+tmp.at(p)+tmp.at(j)==0)
            {
                vector<int> a;
                a.push_back(tmp.at(i));
                a.push_back(tmp.at(p));
                a.push_back(tmp.at(j));
                result.push_back(a);
                cout<<"a.size() "<<a.size()<<endl;
                return;
            }

    }//while
}

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int> > result;
        vector<vector<int> > result_1;
        int i=0;
        int j=num.size()-1;
        int index1=0;
        vector<int> tmp(num);
        sort(tmp.begin(),tmp.end());
        while((j-i>1)&&(index1<tmp.size()))
        {
            int p=(i+j)/2;
            find(i,p,j,tmp,result);
            if(tmp.at(i)+tmp.at(p)+tmp.at(j)<0)
            {
                i++;
                index1++;
            }
            else
            {
               index1++;
                j--;
            }
        }//while
        unique_copy(result.begin(),result.end(),back_inserter(result_1));
        return result_1;
    }
};