g***j
发帖数: 1275 | 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;
}
}; |
g***j
发帖数: 1275 | 2 大家别讨论无聊的话题了，帮我看看程序呀
【在 g***j 的大作中提到】
: 基本思路就是，先把两个的和存起来，并且把相应的index pair存到对应的直的map里
: 面去。
: 然后再把所有的两个的和和target的差算出来，去map里面找，因为map里面同样保存了
: 签名的数字的index，所以，只要后面两个数的最小的index比已有的最大的index大的
: 时候，就能保证不重复了。
: 可惜small set 15个总有一个不过，而且，因为显示问题，看不到哪个不过。哪个大侠
: 帮我看看代码？
: class Solution {
: public:
: vector > fourSum(vector &num, int target) {
|
g***j
发帖数: 1275 | 3 知道哪儿错了，因为保证index不重复，不能保证数字的结果不重复！
比如｛0，0，0，0，0｝，target 0 就错了，回出现都是｛0，0，0，0｝的情况
【在 g***j 的大作中提到】
: 基本思路就是，先把两个的和存起来，并且把相应的index pair存到对应的直的map里
: 面去。
: 然后再把所有的两个的和和target的差算出来，去map里面找，因为map里面同样保存了
: 签名的数字的index，所以，只要后面两个数的最小的index比已有的最大的index大的
: 时候，就能保证不重复了。
: 可惜small set 15个总有一个不过，而且，因为显示问题，看不到哪个不过。哪个大侠
: 帮我看看代码？
: class Solution {
: public:
: vector > fourSum(vector &num, int target) {
|
d**e
发帖数: 6098 | 4 你的code应该可以更简洁一些。
第二个for i/j loop可以不要，直接loop map里面的元素就可以了
【在 g***j 的大作中提到】
: 知道哪儿错了，因为保证index不重复，不能保证数字的结果不重复！
: 比如｛0，0，0，0，0｝，target 0 就错了，回出现都是｛0，0，0，0｝的情况
|
