3-sum問題
3222 ワード
3-sum問題:重複しない配列の3つの数を統計して0の組み合わせに加算します。
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] in = { 3, 4, 5, 6, 1, -6, 8, 21 };
Arrays.sort(in);
//-6,1,3,4,5,6,8,21
Main m = new Main();
int length = in.length;
int count = 0;
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
// (X > j) ,
// (X != -1) , ,
// :-6 1 5 -6 1 5
// 3 , -6 3 3
if (m.binarySearch(in, -(in[i] + in[j])) > j) {
count++;
}
}
}
System.out.println(" "+count+" 3 0 ");
}
//
public int binarySearch(int[] in, int key) {
Arrays.sort(in);
int lo = 0;
int hei = in.length - 1;
while (lo < hei) {
int mid = hei + (lo - hei) / 2;
if (key < in[mid]) {
hei = mid - 1;
} else if (key > in[mid]) {
lo = mid + 1;
} else {
return mid;
}
}
return -1;
}
}