q****m 发帖数: 177 | 1 难道是因为用了 std::sort ?
class Solution {
public:
vector > threeSum(vector &num) {
vector > *set = new vector >;
vector a(num);
sort(a.begin(), a.end());
vector b(num);
for(int k = 0; k < a.size(); ++k)
{
int c = a[k];
for(int j = 0; j < b.size(); ++j)
{
b[j] = -c - a[j];
}
int i = 0;
int j = b.size() -1 ;
while(i < a.size() && j > -1)
{
if (a[i] == b[j])
{
if(i == j)
{
++i;
--j;
continue;
}
if( i == k)
{
++i;
--j;
continue;
}
if( j == k)
{
++i;
--j;
continue;
}
int e = (i < j) ? i : j;
int f = i + j - e ;
int g;
if(k > f)
{
g = k;
}
else if(k > e)
{
g = f;
f = k;
}
else
{
g = f;
f = e;
e = k;
}
vector tmp;
tmp.push_back(a[e]);
tmp.push_back(a[f]);
tmp.push_back(a[g]);
if(find(set->begin(), set->end(), tmp) == set->end())
{
set->push_back(tmp);
}
++i;
--j;
}
else if(a[i] < b[j])
{
++i;
}
else
{
--j;
}
}
}
return *set;
}
}; |
C***U 发帖数: 2406 | 2 是你的计算太复杂了吧
用个set来处理重复试试
不要用那个vector>
【在 q****m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 难道是因为用了 std::sort ? : class Solution { : public: : vector > threeSum(vector &num) { : vector > *set = new vector >; : vector a(num); : sort(a.begin(), a.end()); : vector b(num); : for(int k = 0; k < a.size(); ++k) : {
|
q****m 发帖数: 177 | 3 这个 vector > 是 leetcode里面给出的 prototype阿。
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是你的计算太复杂了吧 : 用个set来处理重复试试 : 不要用那个vector>
|
C***U 发帖数: 2406 | 4 先用set存 再转到vector 比你比较要快吧
【在 q****m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个 vector > 是 leetcode里面给出的 prototype阿。
|
q****m 发帖数: 177 | 5 优化了以后,终于可以 pass large 了. 思路是先对 num 排序. 排序后 num[i] + num
[j] + num[k] = 0中只用考虑 i < j < k的情况
class Solution {
public:
vector > threeSum(vector &num) {
vector > *set = new vector >;
sort(num.begin(), num.end());
vector b;
b.reserve(num.size());
for(int k = 0; k < num.size(); ++k)
{
int c = num[k];
for(int j = 0; j < k; ++j)
{
b[j] = -c - num[j];
}
int i = 0;
int j = k - 1 ;
while(i < k && j > -1)
{
if (num[i] == b[j])
{
if(i >= j)
{
break;
}
vector tmp;
tmp.push_back(num[i]);
tmp.push_back(num[j]);
tmp.push_back(num[k]);
if(find(set->begin(), set->end(), tmp) == set->end())
{
set->push_back(tmp);
}
++i;
--j;
}
else if(num[i] < b[j])
{
++i;
}
else
{
--j;
}
}
}
return *set;
}
};
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先用set存 再转到vector 比你比较要快吧
|
q****m 发帖数: 177 | 6 难道是因为用了 std::sort ?
class Solution {
public:
vector > threeSum(vector &num) {
vector > *set = new vector >;
vector a(num);
sort(a.begin(), a.end());
vector b(num);
for(int k = 0; k < a.size(); ++k)
{
int c = a[k];
for(int j = 0; j < b.size(); ++j)
{
b[j] = -c - a[j];
}
int i = 0;
int j = b.size() -1 ;
while(i < a.size() && j > -1)
{
if (a[i] == b[j])
{
if(i == j)
{
++i;
--j;
continue;
}
if( i == k)
{
++i;
--j;
continue;
}
if( j == k)
{
++i;
--j;
continue;
}
int e = (i < j) ? i : j;
int f = i + j - e ;
int g;
if(k > f)
{
g = k;
}
else if(k > e)
{
g = f;
f = k;
}
else
{
g = f;
f = e;
e = k;
}
vector tmp;
tmp.push_back(a[e]);
tmp.push_back(a[f]);
tmp.push_back(a[g]);
if(find(set->begin(), set->end(), tmp) == set->end())
{
set->push_back(tmp);
}
++i;
--j;
}
else if(a[i] < b[j])
{
++i;
}
else
{
--j;
}
}
}
return *set;
}
}; |
C***U 发帖数: 2406 | 7 是你的计算太复杂了吧
用个set来处理重复试试
不要用那个vector>
【在 q****m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 难道是因为用了 std::sort ? : class Solution { : public: : vector > threeSum(vector &num) { : vector > *set = new vector >; : vector a(num); : sort(a.begin(), a.end()); : vector b(num); : for(int k = 0; k < a.size(); ++k) : {
|
q****m 发帖数: 177 | 8 这个 vector > 是 leetcode里面给出的 prototype阿。
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是你的计算太复杂了吧 : 用个set来处理重复试试 : 不要用那个vector>
|
C***U 发帖数: 2406 | 9 先用set存 再转到vector 比你比较要快吧
【在 q****m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个 vector > 是 leetcode里面给出的 prototype阿。
|
q****m 发帖数: 177 | 10 优化了以后,终于可以 pass large 了. 思路是先对 num 排序. 排序后 num[i] + num
[j] + num[k] = 0中只用考虑 i < j < k的情况
class Solution {
public:
vector > threeSum(vector &num) {
vector > *set = new vector >;
sort(num.begin(), num.end());
vector b;
b.reserve(num.size());
for(int k = 0; k < num.size(); ++k)
{
int c = num[k];
for(int j = 0; j < k; ++j)
{
b[j] = -c - num[j];
}
int i = 0;
int j = k - 1 ;
while(i < k && j > -1)
{
if (num[i] == b[j])
{
if(i >= j)
{
break;
}
vector tmp;
tmp.push_back(num[i]);
tmp.push_back(num[j]);
tmp.push_back(num[k]);
if(find(set->begin(), set->end(), tmp) == set->end())
{
set->push_back(tmp);
}
++i;
--j;
}
else if(num[i] < b[j])
{
++i;
}
else
{
--j;
}
}
}
return *set;
}
};
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先用set存 再转到vector 比你比较要快吧
|
T******7 发帖数: 1419 | 11 what is your code's time complexity in you opinion?
tahnks
num
【在 q****m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 优化了以后,终于可以 pass large 了. 思路是先对 num 排序. 排序后 num[i] + num : [j] + num[k] = 0中只用考虑 i < j < k的情况 : class Solution { : public: : vector > threeSum(vector &num) { : vector > *set = new vector >; : sort(num.begin(), num.end()); : vector b; : b.reserve(num.size()); : for(int k = 0; k < num.size(); ++k)
|
q****m 发帖数: 177 | 12 O(n^2)
【在 T******7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : what is your code's time complexity in you opinion? : tahnks : : num
|