首页 > 代码库 > 3sum 三数之和为0的简单实现

3sum 三数之和为0的简单实现

思路简单:

(1) 三重 for ,符合a+b+c=0的 a,b,c保存在tuple里

(2)tuple保存在set 中,一可去重,二可保持字典序

(3)简单代价就是复杂度很高,O(n^3*logn)

  

typedef tuple<int,int,int> triplet;

triplet sort3(int a,int b,int c){
	if(a<=b){
		if(b>c){
			swap(b,c);
			if(a>b) swap(a,b);
		}
	}
	else{
		swap(a,b);
		if(b>c){
			swap(b,c);
			if(a>b) swap(a,b);
		}
	}
	triplet res = make_tuple(a,b,c);
	return res;
}

vector<vector<int> > threeSum(vector<int> &num) {
    auto sz= num.size(); triplet t3;
    set<triplet> set3;
    vector<vector<int> >res;
    vector<int> mid;
    
    if(sz<3) return res;
    
    for(auto i = 0 ; i<sz-2 ; ++i)
    	for(auto j=i+1 ; j<sz-1 ; ++j )
    		for (auto k=j+1; k<sz ;++k)
    			if(num[i]+num[j]+num[k]==0){
    				t3 = sort3(num[i],num[j],num[k]);
    				set3.insert(t3);
    			}
    for(auto a:set3){
    	mid.clear();
    	mid.push_back(get<0>(a));
    	mid.push_back(get<1>(a));
    	mid.push_back(get<2>(a));
    	res.push_back(mid);
    }
    return res;
}

3sum 三数之和为0的简单实现