public class ThreeSumFast extends Object
ThreeSumFast
class provides static methods for counting
and printing the number of triples in an array of distinct integers that
sum to 0 (ignoring integer overflow).
This implementation uses sorting and binary search and takes time proportional to n^2 log n, where n is the number of integers.
For additional documentation, see Section 1.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
Modifier and Type | Method and Description |
---|---|
static int |
count(int[] a)
Returns the number of triples (i, j, k) with
i < j < k
such that a[i] + a[j] + a[k] == 0 . |
static void |
main(String[] args)
Reads in a sequence of distinct integers from a file, specified as a command-line argument;
counts the number of triples sum to exactly zero; prints out the time to perform
the computation.
|
static void |
printAll(int[] a)
Prints to standard output the (i, j, k) with
i < j < k
such that a[i] + a[j] + a[k] == 0 . |
public static void printAll(int[] a)
i < j < k
such that a[i] + a[j] + a[k] == 0
.a
- the array of integersIllegalArgumentException
- if the array contains duplicate integerspublic static int count(int[] a)
i < j < k
such that a[i] + a[j] + a[k] == 0
.a
- the array of integersi < j < k
such that a[i] + a[j] + a[k] == 0
public static void main(String[] args)
args
- the command-line arguments