【leetcode】15. 3Sum
タイトル
3Sum Total Accepted: 92588 Total Submissions: 521219 Difficulty: Medium
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: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) 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)
コード#コード#
まとめは、まず配列ソートに対応する. 繰り返し要素をスキップすることに注意してください. mapへの応用.
3Sum Total Accepted: 92588 Total Submissions: 521219 Difficulty: Medium
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: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) 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)
コード#コード#
#include
#include
#include
#include
#include
using namespace std;
vector<vector<int>> threeSum(vector<int>& nums) {
vector< vector<int> > ret;
if(nums.size()<3)
return ret;
std::sort( nums.begin(), nums.end() );
if(nums[0]>0||nums.back()<0)
return ret;
std::map<int, int> unmap;
for(int i=0;imap<int, int>::value_type(nums[i],i)); // ,
}
for(int i=0;i2)&&nums[i]<=0;++i) {
for(int j=i+1;j1);++j) {
while(nums[j]==nums[j+1]) {
j++;
}
std::map<int,int>::const_iterator got = unmap.find( 0-nums[i]-nums[j] );
if( got!=unmap.end() &&( got->second > j) ) {
vector<int> a;
a.push_back(nums[i]);
a.push_back(nums[j]);
a.push_back(nums[got->second]);
ret.push_back( a );
}
}
}
std::sort(ret.begin(), ret.end());
auto iter = std::unique( ret.begin(), ret.end() );
ret.resize( std::distance( ret.begin(), iter ) );
return ret;
}
int main(int argc,char *argv[]) {
vector<int> nums={-9,14,-7,-8,9,1,-10,-8,13,12,6,9,3,-3,-15,-15,1,8,-7,-4,-6,8,2,-10,8,11,-15,3,0,-11,-1,-1,10,0,6,5,-14,3,12,-15,-7,-5,9,11,-1,1,3,-15,-5,11,-12,-4,-4,-2,-6,-10,-6,-6,0,2,-9,14,-14,-14,-9,-1,-2,-7,-12,-13,-15,-4,-3,1,14,3,-12,3,3,-10,-9,-1,-7,3,12,-6,0,13,4,-15,0,2,6,1,3,13,8,-13,13,11,11,13,14,-6};
struct timeval tv1,tv2;
struct timezone tz;
int time1 = gettimeofday(&tv1,&tz);
//func();
vector< vector<int> > ret = threeSum( nums );
int time2 = gettimeofday(&tv2,&tz);
cout << "time consuming:" << tv2.tv_usec - tv1.tv_usec <<"us"<< endl;
for(int i=0;ifor(int j=0;j0].size();++j) {
cout<",";
}
cout<return 0;
}
まとめ