j**y 发帖数: 462 | 1 Find a pair of numbers that sums up to zero (or any other number), then
find three (and then four) numbers that sum up to zero
有什么好的方法? 多谢 |
j**y 发帖数: 462 | 2 俺只会把所有3个数或4个数组合列出来
有啥好办法? |
g***s 发帖数: 3811 | |
j**y 发帖数: 462 | 4 找了半天也没找到下面算法
There is a simple algorithm to solve 3SUM in O(n2) time.
有code吗 多谢
【在 g***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : http://en.wikipedia.org/wiki/3SUM
|
j**y 发帖数: 462 | 5
public static int count(int[] a) {
int N = a.length;
Arrays.sort(a);
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = i+1; j < N; j++) {
int k = Arrays.binarySearch(a, -(a[i] + a[j]));
if (k > j) cnt++;
}
}
return cnt;
}
【在 j**y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 找了半天也没找到下面算法 : There is a simple algorithm to solve 3SUM in O(n2) time. : 有code吗 多谢
|
g**e 发帖数: 6127 | 6 this is O(n^2*lgn). there is o(n^2) algorithm.
use head and tail pointers in your second loop to do the search.
【在 j**y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : public static int count(int[] a) { : int N = a.length; : Arrays.sort(a); : int cnt = 0; : for (int i = 0; i < N; i++) { : for (int j = i+1; j < N; j++) { : int k = Arrays.binarySearch(a, -(a[i] + a[j])); : if (k > j) cnt++; : }
|
P********l 发帖数: 452 | 7 http://www.sureinterview.com/shwqst/81004
http://www.sureinterview.com/schlsc?q=sum#
【在 j**y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Find a pair of numbers that sums up to zero (or any other number), then : find three (and then four) numbers that sum up to zero : 有什么好的方法? 多谢
|