g***j
发帖数: 1275 | 1 为啥这个可以过？ 下面这个时间复杂度是 O^3 吧？
class Solution {
public:
vector > fourSum(vector &num, int target) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
vector tmp;
vector> results;
if(num.empty()) return results;
sort(num.begin(), num.end());
for(int i=0; i
{
for(int j=i+1; j
{
int temp = target - num[j] - num[i];
int start = j+1, end = num.size()-1;
while(start
{
if(num[start]+num[end]==temp)
{
tmp.push_back(num[i]);
tmp.push_back(num[j]);
tmp.push_back(num[start]);
tmp.push_back(num[end]);
results.push_back(tmp);
tmp.clear();
start++;
end--;
while(start
while(start
}
else if(num[start]+num[end]
{
start++;
while(start
}
else
{
end--;
while(start
}
}
while(j
}
while(i
}
return results;
}
}; | m******3
发帖数: 346 | 2 应该不是N^3,最里面一层是binary search, 应该复杂度是N^2LogN
reused
【在 g***j 的大作中提到】
: 为啥这个可以过？ 下面这个时间复杂度是 O^3 吧？
: class Solution {
: public:
: vector > fourSum(vector &num, int target) {
: // Note: The Solution object is instantiated only once and is reused
: by each test case.
: vector tmp;
: vector> results;
: if(num.empty()) return results;
: sort(num.begin(), num.end());
| y*******8
发帖数: 112 | | g***j
发帖数: 1275 | 4 are you sure?
里面明明是两个指针
【在 m******3 的大作中提到】
: 应该不是N^3,最里面一层是binary search, 应该复杂度是N^2LogN
:
: reused
|
|
