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 的大作中提到】
: 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 的大作中提到】
: 找了半天也没找到下面算法
: 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 的大作中提到】
:
: 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 的大作中提到】
: 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
: 有什么好的方法？ 多谢
|
