本文共 4288 字，大约阅读时间需要 14 分钟。
#include #include #include #include #include #include #include using namespace std;/*问题: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]]triplets:三元组分析:之前一道题是计算两个数的和，然后是从两边向中间逼近。 如果采用暴力破解：那么需要一个三层循环，时间复杂度为O(n^3) 如果先排序，从小到大，那么如果假设: a < b < c,必定有c大于0，a小于0，至于b=-a-c 如果去遍历a,c从两头向中间，并且设定一个哈希表，那么查询b在哈希表中的时间是O(1)， 则时间复杂度为O(n^2)。一种更简单的方法：先排序，根据a+b+c=0,所以b=-(a+c)初始时：设定a是最左边元素，c是最右边元素，假设数组为A计算b=-(a+c),如果b在哈希表中，说明成立，判断该三元组如果不重复就直接输出；否则，说明找不到。 这两种情况都需要使得最左边下标累加，最右边下标累减。因为a和c分别是最小，最大，且当前情况都已经匹配过如果出现: b > c,说明a太小，使得条件不满足，则使得左边下标累加 b < a,说明c太大， 右边下标累减整体时间复杂度为O(NlogN)发现hash_map不能用:Line 17: 'hash_map' was not declared in this scope如果b在哈希表hash 即 <值，出现次数> 中b果然发现递归超时。一种解法：根据两数和的想法，先对数组排序，首先确定第一个数a，然后设定两数和为-a,则两数和采用从两头向中间逼近的方法，两数和时间复杂度O(n)，遍历数组中每个元素作为第一个数时间复杂度为O(n)，总时间复杂度为O(n^2)。输入:15-4 -2 -2 -2 0 1 2 2 2 3 3 4 4 6 66-1 0 1 2 -1 -460 0 0 0 0 06-1 -1 -1 -1 2 21020 0 输出:-4-2 6,-4 0 4 , -4 1 3, -4 2 2 , -2 -2 4 , -2 0 2-1 0 1, -1 -1 20 0 0-1 -1 2no resultno result关键：1 根据两数和的想法，先对数组排序，首先确定第一个数a，然后设定两数和为-a,则两数和采用从两头向中间逼近的方法，两数和时间复杂度O(n)，遍历数组中每个元素作为第一个数时间复杂度为O(n)，总时间复杂度为O(n^2)。*/class Result{public: Result(){} Result(int min , int mid , int max):_min(min),_mid(mid),_max(max){} bool operator < (const Result& result) const //仿函数，用于set排序 { if(_min != result._min) { return _min < result._min ; } else if(_mid != result._mid) { return _mid < result._mid; } else { return _max < result._max; } } int _min; int _mid; int _max;};class Solution {public: int min(int a , int b ,int c) { int minValue = a < b ? a : b; int minVal = c < minValue ? c : minValue; return minVal; } int max(int a , int b , int c) { int maxValue = a > b ? a : b; int maxVal = c > maxValue ? c : maxValue; return maxVal; } //计算两数之和，结果可能多个。如何去重？已经有一个数被使用了，这个数不能出现在求两数之和的结果中，遇到该下标直接跳过 void twoSum(vector & nums , int value , int selectIndex, set >& results) { if(nums.empty()) { return ; } int sum; int size = nums.size(); int low = 0; int high = size - 1; int minValue , midValue , maxValue; while(low < high) { //如果左边的数字等于已经选择的数字，则low++ if(selectIndex == low) { low++; } else if(selectIndex == high) { high--; } //如果发现不满足，则退出 if(low >= high) { break; } //如果两数之和小于目标值，则令low++;两数之和大于目标值，high--;如果两数之和等于目标值，则low++,high-- sum = nums.at(low) + nums.at(high); if(sum < value) { low++; } else if(sum > value) { high--; } //找到了，存入结果集，存入的结果集需要确定三者的大小 else { minValue = min( nums.at(low) ,nums.at(high) , nums.at(selectIndex) ); maxValue = max( nums.at(low) ,nums.at(high) , nums.at(selectIndex) ); midValue = sum + nums.at(selectIndex) - minValue - maxValue; Result result(minValue , midValue , maxValue); results.insert(result); low++; high--; } } } /* 本质上确定第一个数之后，随后两个数的确定可以采用两数之和的方法(从两头向中间逼近)，但要去除掉重复的，判重部分单独提取一个方法。 */ vector > threeSum(vector & nums) { vector > resultVector; //遍历每一个数作为第一个数，确定其余两数之和 if(nums.empty()) { return resultVector; } //先排序 sort(nums.begin() , nums.end()); int size = nums.size(); int a; int target; int selectIndex; set > results; for(int i = 0 ; i < size ; i++) { //依次选择第一个数，那么第一个数就不能再作为第二个数，第三个数 a = nums.at(i); selectIndex = i; //两个数的目标和为: -a target = -a; twoSum(nums , target , selectIndex , results); } //计算出结果后，输出结果 for(set >::iterator it = results.begin() ; it != results.end() ; it++) { vector resultVec; resultVec.push_back(it->_min); resultVec.push_back(it->_mid); resultVec.push_back(it->_max); resultVector.push_back(resultVec); } return resultVector; }};void print(vector< vector >& results){ if(results.empty()) { cout << "no result" << endl; return; } int size = results.size(); for(int i = 0 ; i < size ; i++) { vector result = results.at(i); int len = result.size(); for(int j = 0; j < len ; j++) { cout << result.at(j) << " "; } cout << ","; } cout << endl;}void process(){ int num; vector nums; vector< vector > results; int value; while(cin >> num) { nums.clear(); for(int i = 0 ; i < num ; i++) { cin >> value; nums.push_back(value); } Solution solution; results = solution.threeSum(nums); print(results); }}int main(int argc , char* argv[]){ process(); getchar(); return 0;}
转载地址：http://jhofn.baihongyu.com/