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: 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] ]*
解题过程 : 将输入的数分成三组，正数，负数，零。 每次从正数中和负数中取出一个，然后相加，结果分三种情况：（1）结果为0，就看有没有零，有零的话就可以把这一组加入结果中，否则break；（2）结果为负数，那么就在正数数组中寻找相加为零的数，若找到就加入结果中，否则break；（3）结果为正数，那么就在正数数组中寻找相加为零的数，若找到就加入结果中，否则break （4）如果出现了三个零的情况，则把三个零放在一组加入到结果。 最后把result用sort排序以后再用unique和erase去除重复的组。代码如下：
vector<vector<int>> threeSum(vector<int>& nums) { //将数组分成正数，负数和零三个数组 int zheng[10000]; //正数 int fu[10000]; //负数 int ling[10000]; //零 int zheng1=0,fu1=0,ling1=0; int fu3,zheng3; vector<int> temp; vector<vector<int>> result; //结果 for(vector<int>::const_iterator iter = nums.begin(); iter < nums.end();*iter++ ){ if(*iter > 0) zheng[zheng1++]= *iter; if(*iter == 0) ling[ling1++] = *iter; if(*iter < 0) fu[fu1++] = *iter; } // for(int zheng2 = 0; zheng2 < zheng1 ; zheng2++){ for(int fu2 = 0; fu2 < fu1; fu2++){ int sum = zheng[zheng2] + fu[fu2]; if(sum > 0){ //两书之和为正，再找一个负数 for( fu3 = 0; fu3 < fu1; fu3++){ if(sum + fu[fu3] == 0 && fu2!=fu3){ temp.push_back(fu[fu2]); temp.push_back(fu[fu3]); temp.push_back(zheng[zheng2]); sort(temp.begin(),temp.end()); result.push_back(temp); temp.clear(); break; } } } else if( sum == 0){ //如果正负两个数相加等于零，则看是否有零，有则加入结果 if(ling1 != 0){ temp.push_back(fu[fu2]); temp.push_back(0); temp.push_back(zheng[zheng2]); sort(temp.begin(),temp.end()); result.push_back(temp); temp.clear(); break; } else continue; } else if(sum < 0){ //两书之和为负，再找一个正数 for( zheng3 = 0; zheng3 < zheng1; zheng3++ ){ if(sum + zheng[zheng3] == 0 && zheng2!=zheng3){ temp.push_back(fu[fu2]); temp.push_back(zheng[zheng3]); temp.push_back(zheng[zheng2]); sort(temp.begin(),temp.end()); result.push_back(temp); temp.clear(); break; } } } }//for }//for if(ling1 >= 3){ temp.push_back(0); temp.push_back(0); temp.push_back(0); result.push_back(temp); temp.clear(); } std::sort(result.begin(),result.end()); vector<vector<int>>::iterator unique_iter = unique(result.begin(),result.end()); result.erase(unique_iter,result.end()); // con.erase(std::result(result.begin(),result.end()),result.end()); return result; }