Bergen郡NJ的AMEX的smal business大家都去哪里消费？ (转载)# Money - 海外理财
f*m
1 楼
题目：
在网上搜了一个code,如下，做了一些小修改，可是总过不了online judge.大家能发一
个能通过judge的(n^2) code吗？谢谢。
vector > fourSum(vector &num, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int n = num.size();
vector > result;
map > sums;
for (int i = 0; i < n; ++i) {
// 'sums' hastable holds all possible sums a[k] + a[l]
// where k and l are both less than i
for (int j = i + 1; j < n; ++j) {
int current = num[i] + num[j];
int rest = target - current;
// Now we need to find if there're different numbers k and l
// such that a[k] + a[l] == rest and k < i and l < i
// but we have 'sums' hashtable prepared for that
if (sums.count(rest) != 0) {
// found it
vector t;
t.push_back(sums[rest].first);
t.push_back(sums[rest].second);
t.push_back(num[i]);
t.push_back(num[j]);
}
}
// now let's put in 'sums' hashtable all possible sums
// a[i] + a[k] where k < i
for (int k = 0; k < i; ++k) {
sums[num[i] + num[k]] = pair (i, k);
}
}
return result;
}
在网上搜了一个code,如下，做了一些小修改，可是总过不了online judge.大家能发一
个能通过judge的(n^2) code吗？谢谢。
vector
// Start typing your C/C++ solution below
// DO NOT write int main() function
int n = num.size();
vector
map
for (int i = 0; i < n; ++i) {
// 'sums' hastable holds all possible sums a[k] + a[l]
// where k and l are both less than i
for (int j = i + 1; j < n; ++j) {
int current = num[i] + num[j];
int rest = target - current;
// Now we need to find if there're different numbers k and l
// such that a[k] + a[l] == rest and k < i and l < i
// but we have 'sums' hashtable prepared for that
if (sums.count(rest) != 0) {
// found it
vector
t.push_back(sums[rest].first);
t.push_back(sums[rest].second);
t.push_back(num[i]);
t.push_back(num[j]);
}
}
// now let's put in 'sums' hashtable all possible sums
// a[i] + a[k] where k < i
for (int k = 0; k < i; ++k) {
sums[num[i] + num[k]] = pair
}
}
return result;
}
