一秒钟变格格# pets - 心有所宠
g*j
1 楼
基本思路就是,先把两个的和存起来,并且把相应的index pair存到对应的直的map里
面去。
然后再把所有的两个的和和target的差算出来,去map里面找,因为map里面同样保存了
签名的数字的index,所以,只要后面两个数的最小的index比已有的最大的index大的
时候,就能保证不重复了。
可惜small set 15个总有一个不过,而且,因为显示问题,看不到哪个不过。哪个大侠
帮我看看代码?
class Solution {
public:
vector > fourSum(vector &num, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int n = num.size();
vector > results;
if(n <= 3) return results;
map > > myMap;
map > >::iterator iter;
for(int i = 0; i < n; i++) {
for(int j = i+1; j < n; j++) {
int sum = num[i] + num[j];
iter = myMap.find(sum);
if(iter == myMap.end()) {
vector > newPair;
newPair.push_back(pair(i, j));
myMap[sum] = newPair;
} else {
(iter->second).push_back(pair(i, j));
}
}
}
for(int i = 0; i < n; i++) {
for(int j = i+1; j < n; j++) {
int sum = target - num[i] - num[j];
iter = myMap.find(sum);
if(iter != myMap.end()) {
vector > pairs = iter->second;
int size = pairs.size();
for(int k = 0; k < size; k++) {
if(i > pairs[k].second) {
vector entry;
entry.push_back(num[i]);
entry.push_back(num[j]);
entry.push_back(num[pairs[k].first]);
entry.push_back(num[pairs[k].second]);
sort(entry.begin(), entry.end());
results.push_back(entry);
}
}
}
}
}
return results;
}
};
面去。
然后再把所有的两个的和和target的差算出来,去map里面找,因为map里面同样保存了
签名的数字的index,所以,只要后面两个数的最小的index比已有的最大的index大的
时候,就能保证不重复了。
可惜small set 15个总有一个不过,而且,因为显示问题,看不到哪个不过。哪个大侠
帮我看看代码?
class Solution {
public:
vector
// Start typing your C/C++ solution below
// DO NOT write int main() function
int n = num.size();
vector
if(n <= 3) return results;
map
map
for(int i = 0; i < n; i++) {
for(int j = i+1; j < n; j++) {
int sum = num[i] + num[j];
iter = myMap.find(sum);
if(iter == myMap.end()) {
vector
newPair.push_back(pair
myMap[sum] = newPair;
} else {
(iter->second).push_back(pair
}
}
}
for(int i = 0; i < n; i++) {
for(int j = i+1; j < n; j++) {
int sum = target - num[i] - num[j];
iter = myMap.find(sum);
if(iter != myMap.end()) {
vector
int size = pairs.size();
for(int k = 0; k < size; k++) {
if(i > pairs[k].second) {
vector
entry.push_back(num[i]);
entry.push_back(num[j]);
entry.push_back(num[pairs[k].first]);
entry.push_back(num[pairs[k].second]);
sort(entry.begin(), entry.end());
results.push_back(entry);
}
}
}
}
}
return results;
}
};