i******t
发帖数: 798 | |
h****e
发帖数: 2125 | 2 用set呗。
【在 i******t 的大作中提到】
: thx
|
i******t
发帖数: 798 | 3 这个我知道 除了这个呢 用set有点投机吧
【在 h****e 的大作中提到】
: 用set呗。
|
l******i
发帖数: 194 | 4 移动到不相等的呗。。。4 sum我也移动了。。。 |
b******g
发帖数: 3616 | 5 不必用set。
假设A[i] = A[i+1] = A[i+2] = x != A[i+3]。
在A[i]的时候解2 sum问题以后，已经把包含一个x，两个x和三个x的解都考察过了。所
以下一步移动时直接移动到A[i+3]来解2 sum问题就行了。
【在 i******t 的大作中提到】
: 这个我知道 除了这个呢 用set有点投机吧
|
i******t
发帖数: 798 | 6 那 k sum 如何避免duplicate 呢？
【在 b******g 的大作中提到】
: 不必用set。
: 假设A[i] = A[i+1] = A[i+2] = x != A[i+3]。
: 在A[i]的时候解2 sum问题以后，已经把包含一个x，两个x和三个x的解都考察过了。所
: 以下一步移动时直接移动到A[i+3]来解2 sum问题就行了。
|
r*******h
发帖数: 315 | 7 一样的思路，每层循环都需要把后面重复的跳过去。
【在 i******t 的大作中提到】
: 那 k sum 如何避免duplicate 呢？
|
i******t
发帖数: 798 | 8 en多谢指点
假设2sum
是这个意思吗
prei =-10000;
for(int i =0; i
{
if(prei == A[i])
{
continue;
}
prei = a[i];
prej =-10000;
for(int j =i+1; j
{
if(prej == A[j])
{
continue;
}
prej = a[j];
// do sum test....
}
}
是这个意思吧
【在 r*******h 的大作中提到】
: 一样的思路，每层循环都需要把后面重复的跳过去。
|
r*******h
发帖数: 315 | 9 差不多，但是前提是数组要排好序，如果排好序，2sum的更好解法是双指针，从两头
skip重复的。
【在 i******t 的大作中提到】
: en多谢指点
: 假设2sum
: 是这个意思吗
: prei =-10000;
: for(int i =0; i: {
: if(prei == A[i])
: {
: continue;
: }
|
l********g
发帖数: 372 | 10 对于k sum, k>=3的，都先用nlogn排序后进行上头说的那样的跳跃法子来进行两指针的
2sum，复杂度应该都是O(n^(k-1))。 2sum本身因为要O(n)了所以无序的大家一般不会
先sort。 |
