本文共 3419 字，大约阅读时间需要 11 分钟。
#include#include #include #include #include using namespace std;/*问题:Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.Note: The solution set must not contain duplicate quadruplets.For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.分析:用3Sum来做。罗列第一个数和第二个数，时间复杂度为O(n^3)A solution set is:[ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2]输入:6(数组元素个数) 0(目标和)1 0 -1 0 -2 29 120 4 -5 2 -2 4 2 -1 4输出:-1 0 0 1, -2 -1 1 2, -2 0 0 20 4 4 4, 2 2 4 4关键:1 4Sum用3Sum来做。罗列第一个数和第二个数，时间复杂度为O(n^3)for(int i = 0 ; i < size - 2 ; i++){ int target_3 = target - nums.at(i); for(int j = i + 1 ; j < size - 1; j++) { int target_2 = target_3 - nums.at(j); int low = j + 1; int high = size - 1; while(low < high) { sum = nums.at(low) + nums.at(high); if(sum < target_2) { low++; } else if(sum > target_2) { high--; } else { Result result(nums.at(i) , nums.at(j) , nums.at(low) , nums.at(high)); setResult.insert(result); low++; high--; } } }}*/typedef struct Result{ Result(){} Result(int min ,int mid1 , int mid2 , int max):_min(min),_mid1(mid1),_mid2(mid2),_max(max){} bool operator < (const Result& result) const { if(_min != result._min) { return _min < result._min; } else if(_mid1 != result._mid1) { return _mid1 < result._mid1; } else if(_mid2 != result._mid2) { return _mid2 < result._mid2; } else { return _max < result._max; } } int _min; int _mid1;//次最小 int _mid2;//次最大 int _max;}Result;class Solution {public: vector > fourSum(vector & nums, int target) { vector > results; if(nums.empty() || nums.size() < 4) { return results; } int size = nums.size(); sort(nums.begin() , nums.end()); int sum; set > setResult; //这里的关键是罗列的时候:我已经实现罗列的a<=b,后续确定的另外两个数c,d有:a <= b <= c <= d //这样罗列比如:a=A[1], b=A[3],那么是否c可以为A[2]?不可以，已经假定了顺序。那么也不会存在判重的问题 for(int i = 0 ; i < size - 2 ; i++) { int target_3 = target - nums.at(i); for(int j = i + 1 ; j < size - 1; j++) { int target_2 = target_3 - nums.at(j); int low = j + 1; int high = size - 1; while(low < high) { sum = nums.at(low) + nums.at(high); if(sum < target_2) { low++; } else if(sum > target_2) { high--; } else { Result result(nums.at(i) , nums.at(j) , nums.at(low) , nums.at(high)); setResult.insert(result); low++; high--; } } } } //返回结果 for(set >::iterator it = setResult.begin() ; it != setResult.end() ; it++) { vector vecResult; //vector {nums[i],nums[j],nums[left],nums[right]} vecResult.push_back(it->_min); vecResult.push_back(it->_mid1); vecResult.push_back(it->_mid2); vecResult.push_back(it->_max); results.push_back(vecResult); } return results; }};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; int target; while(cin >> num >> target) { nums.clear(); for(int i = 0 ; i < num ; i++) { cin >> value; nums.push_back(value); } Solution solution; results = solution.fourSum(nums , target); print(results); }}int main(int argc , char* argv[]){ process(); getchar(); return 0;}
转载地址：http://shofn.baihongyu.com/