首页 > 代码库 > 4Sum
4Sum
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:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
The solution set must not contain duplicate quadruplets.
For example, given array S = {1 0 -1 0 -2 2}, and target = 0. A solution set is: (-1, 0, 0, 1) (-2, -1, 1, 2) (-2, 0, 0, 2)思路：
1 class Solution { 2 public: 3 vector<vector<int>> fourSum( vector<int> &num, int target ) { 4 set<vector<int>> quadrupletSet; 5 sort( num.begin(), num.end() ); 6 vector<int> quadruplet( 4, -1 ); 7 for( int s1 = (int)num.size()-4; s1 >= 0; --s1 ) { 8 if( target < 4*num[s1] ) { continue; } 9 for( int e1 = (int)num.size()-1; e1 > s1+2; --e1 ) {10 if( target > 4*num[e1] ) { break; }11 int s2 = s1+1, e2 = e1-1;12 while( s2 < e2 ) {13 int sum = num[s1] + num[e1] + num[s2] + num[e2];14 if( sum == target ) {15 quadruplet[0] = num[s1];16 quadruplet[3] = num[e1];17 quadruplet[1] = num[s2];18 quadruplet[2] = num[e2];19 quadrupletSet.insert( quadruplet );20 ++s2; --e2;21 } else if( sum < target ) {22 ++s2;23 } else {24 --e2;25 }26 }27 }28 }29 vector<vector<int>> quadruplets;30 for( auto iter = quadrupletSet.begin(); iter != quadrupletSet.end(); ++iter ) {31 quadruplets.push_back( *iter );32 }33 return quadruplets;34 }35 };
4Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。