Class ThreeSumFast

java.lang.Object

ThreeSumFast

public class ThreeSumFast
extends java.lang.Object

The 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.

Constructor Summary

Constructors

Constructor and Description
ThreeSumFast()

Method Summary

Methods

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(java.lang.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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ThreeSumFast

public ThreeSumFast()

Method Detail

printAll

public 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.

Parameters:

a - the array of integers

Throws:

java.lang.IllegalArgumentException - if the array contains duplicate integers

count

public 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.

Parameters:

a - the array of integers

Returns:

the number of triples (i, j, k) with i < j < k such that a[i] + a[j] + a[k] == 0

main

public static void main(java.lang.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.