g********c
发帖数: 23 | 1 我在网上找了个答案
http://yucoding.blogspot.in/2012/12/leetcode-question-3-4-sum.h
他先是把所有元素两两相加，存进multimap做了个hash，
然后在这个multimap里依次两两相加看是否等于target。
我感觉他的解法很费时间啊，超过O(n^4)了吧？（因为首先构建好multimap的size是O(
n^2)，然后再两层for循环）
我之前用3sum那种方法写的，左右移动指针，O(n^3)，不超时，但是最近提交都显示超
时。
哪里有不超时C++的答案呢？ | c*******0
发帖数: 162 | 2 这个代码O(n^3), 但不超时。
vector > fourSum(vector &num, int target) {
vector > rst;
if(num.size() <= 3) return rst;
std::sort(num.begin(), num.end());
int len = num.size();
for(int i = 0; i < num.size() - 3; i++){
if(i > 0 && num[i] == num[i-1]) continue;
for(int j = i + 1; j < num.size() - 2; j++){
if(j > i + 1 && num[j] == num[j-1])continue;
int l = j + 1, r = len - 1;
while(l < r){
int sum = num[i] + num[j] + num[l] + num[r] ;
if(sum == target){
vector item = {num[i], num[j], num[l], num[r]};
rst.push_back(item);
r--;
while(l < r && num[r] == num[r+1]) r--;
l++;
while(l < r && num[l] == num[l-1]) l++;
}else if(sum > target)
r--;
else
l++;
}
}
}
return rst;
} | g********c
发帖数: 23 | 3 有没有O（n^2 * lg n）的代码呢？网上都说自己的复杂度低，可是一看都很高
【在 c*******0 的大作中提到】
: 这个代码O(n^3), 但不超时。
: vector > fourSum(vector &num, int target) {
: vector > rst;
: if(num.size() <= 3) return rst;
: std::sort(num.begin(), num.end());
:
: int len = num.size();
: for(int i = 0; i < num.size() - 3; i++){
: if(i > 0 && num[i] == num[i-1]) continue;
: for(int j = i + 1; j < num.size() - 2; j++){
| x********u
发帖数: 1061 | 4 我感觉不可能有最差O（n^2 * lg n）算法，最多是期望能达到这个
【在 g********c 的大作中提到】
: 有没有O（n^2 * lg n）的代码呢？网上都说自己的复杂度低，可是一看都很高
|
|
