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 的大作中提到】
: 难道是因为用了 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 的大作中提到】
: 是你的计算太复杂了吧
: 用个set来处理重复试试
: 不要用那个vector>
|
C***U
发帖数: 2406 | 4 先用set存 再转到vector 比你比较要快吧
【在 q****m 的大作中提到】
: 这个 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 的大作中提到】
: 先用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 的大作中提到】
: 难道是因为用了 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 的大作中提到】
: 是你的计算太复杂了吧
: 用个set来处理重复试试
: 不要用那个vector>
|
C***U
发帖数: 2406 | 9 先用set存 再转到vector 比你比较要快吧
【在 q****m 的大作中提到】
: 这个 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 的大作中提到】
: 先用set存 再转到vector 比你比较要快吧
|
T******7
发帖数: 1419 | 11 what is your code's time complexity in you opinion?
tahnks
num
【在 q****m 的大作中提到】
: 优化了以后，终于可以 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 的大作中提到】
: what is your code's time complexity in you opinion?
: tahnks
:
: num
|
