l********r
发帖数: 140 | 1 Given 3 sorted arrays, array a, array b, array c. find all pairs where a[i]
+ b[j] = c[k].
We can convert it to 3SUM for a nxn solution, but that doesn't used the "
sorted" property. |
x****g
发帖数: 1512 | |
r****c
发帖数: 2585 | |
x****g
发帖数: 1512 | 4 排序数组本身无dup?
【在 r****c 的大作中提到】
: 怎么可能nlogn
: 可以有O（n^2)组解
|
e***s
发帖数: 799 | 5 这题用两个hash应该可以O(max(m,n) + l)，m, n, l分别是a, b, c的长度。 |
x****g
发帖数: 1512 | 6 展开说说，表示不解. hash求和的新思路也有兴趣学习，呵呵。
最差怎么都是o(n^2)
即使每个都无dup,像
A=1,2,3,4,5...n
B=n,n-1,....1
C=n+1,n+2......n+n
那么n+1就有n对
n+2就n-1对
...n+n就1对
计算n(n+1)/2.....
【在 e***s 的大作中提到】
: 这题用两个hash应该可以O(max(m,n) + l)，m, n, l分别是a, b, c的长度。
|
e***s
发帖数: 799 | 7 之前看错题了，以为返回是否存在a[i] + b[j] = c[k]
但是复杂度是一样的。
public static boolean another3Sum(int[] A, int[] B, int[] C){
HashSet ha = new HashSet();
HashSet hb = new HashSet();
int i = 0, j = 0;
for(int k = 0; k < C.length; k++){
if(i < A.length && j < B.length){
if(A[i] + B[j] > C[k]){
if(ha.contains(C[k] - B[j]) || hb.contains(C[k] - A[i]))
return true;
}
else if (A[i] + B[j] < C[k]){
ha.add(A[i++]);
hb.add(B[j++]);
k--;
}
else return true;
} else if(i >= A.length){
if(ha.contains(C[k] - B[j])) return true;
else{
hb.add(B[j++]);
k--;
}
} else if(j >= B.length){
if(hb.contains(C[k] - A[i])) return true;
else{
ha.add(A[i++]);
k--;
}
}
}
return false;
}
【在 x****g 的大作中提到】
: 展开说说，表示不解. hash求和的新思路也有兴趣学习，呵呵。
: 最差怎么都是o(n^2)
: 即使每个都无dup,像
: A=1,2,3,4,5...n
: B=n,n-1,....1
: C=n+1,n+2......n+n
: 那么n+1就有n对
: n+2就n-1对
: ...n+n就1对
: 计算n(n+1)/2.....
|
x****g
发帖数: 1512 | 8 这个显然不一样。
代码没细看，但觉得不可能对。
简单举个例子：
a[0]=3;
b[0]=4;
c[0]=6
所以冲上来
a[i]+b[j]>c[k]
但是不能满足
if(ha.contains(C[k] - B[j]) || hb.contains(C[k] - A[i]))
return true;
完了直接死循环了.....
懒得琢磨了，呵呵。
))
【在 e***s 的大作中提到】
: 之前看错题了，以为返回是否存在a[i] + b[j] = c[k]
: 但是复杂度是一样的。
: public static boolean another3Sum(int[] A, int[] B, int[] C){
: HashSet ha = new HashSet();
: HashSet hb = new HashSet();
: int i = 0, j = 0;
: for(int k = 0; k < C.length; k++){
: if(i < A.length && j < B.length){
: if(A[i] + B[j] > C[k]){
: if(ha.contains(C[k] - B[j]) || hb.contains(C[k] - A[i]))
|
e***s
发帖数: 799 | 9 我晕了，test case你跑过不？
【在 x****g 的大作中提到】
: 这个显然不一样。
: 代码没细看，但觉得不可能对。
: 简单举个例子：
: a[0]=3;
: b[0]=4;
: c[0]=6
: 所以冲上来
: a[i]+b[j]>c[k]
: 但是不能满足
: if(ha.contains(C[k] - B[j]) || hb.contains(C[k] - A[i]))
|
g****1
发帖数: 89 | 10 我觉得外星人挺有道理
不过好像在处理a或b到头时要考虑k++的情况
【在 x****g 的大作中提到】
: 这个显然不一样。
: 代码没细看，但觉得不可能对。
: 简单举个例子：
: a[0]=3;
: b[0]=4;
: c[0]=6
: 所以冲上来
: a[i]+b[j]>c[k]
: 但是不能满足
: if(ha.contains(C[k] - B[j]) || hb.contains(C[k] - A[i]))
|
|
|
x****g
发帖数: 1512 | 11 确实，我没能理解对，挺好的，继续学习中。
【在 g****1 的大作中提到】
: 我觉得外星人挺有道理
: 不过好像在处理a或b到头时要考虑k++的情况
|
l********r
发帖数: 140 | |
g****1
发帖数: 89 | 13 嗯，好像有问题。一旦 a[i]+b[j]>c[k] 导致k++, 就失去了以后比较c[k]的机会
【在 x****g 的大作中提到】
: 确实，我没能理解对，挺好的，继续学习中。
|
e***s
发帖数: 799 | 14 因为3个数组都是sorted的， a[i]+b[j] > c[k] 证明 c[k] 肯定不能由a[0..i]和b[0.
.j]组合而成。
【在 g****1 的大作中提到】
: 嗯，好像有问题。一旦 a[i]+b[j]>c[k] 导致k++, 就失去了以后比较c[k]的机会
|
b****f
发帖数: 138 | |
x****g
发帖数: 1512 | 16 但是c[k]失去了由a[0..i]和b[j+1....n]或者a[i+1...]和b[0...j]构成的判定机会？
a 2 5 6
b 1 3 10
c 7 9
开始i=0;j=0;k=0;
2+1 < 7 所以 i++,j++,k不动
5+3 > 7 所以判定7-5,7-3失败，这个时候k++
所以7从此失去了判定的机会？没机会判出6+1=7这一项了。
不知道我看错没，不能怪我啊，这个写的太邪乎，呵呵。
0.
【在 e***s 的大作中提到】
: 因为3个数组都是sorted的， a[i]+b[j] > c[k] 证明 c[k] 肯定不能由a[0..i]和b[0.
: .j]组合而成。
|
e***s
发帖数: 799 | 17 确实是这样，我错了。
我也没想到能比 O(min(m * n, l))更好的了，m, n是3个数组长度较短的两个。
【在 x****g 的大作中提到】
: 但是c[k]失去了由a[0..i]和b[j+1....n]或者a[i+1...]和b[0...j]构成的判定机会？
: a 2 5 6
: b 1 3 10
: c 7 9
: 开始i=0;j=0;k=0;
: 2+1 < 7 所以 i++,j++,k不动
: 5+3 > 7 所以判定7-5,7-3失败，这个时候k++
: 所以7从此失去了判定的机会？没机会判出6+1=7这一项了。
: 不知道我看错没，不能怪我啊，这个写的太邪乎，呵呵。
:
|
s******t
发帖数: 229 | 18 我来写个最靠谱的：
先用young，O(n)搞定每一个c[k],一共n个c[k],O(n2)
不过没有利用上sorted的c这个条件，估计还是不太好。。。嘻嘻 |
