edu.princeton.cs.algs4

Class ThreeSumFast

Object

edu.princeton.cs.algs4.ThreeSumFast

public class ThreeSumFast
extends 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.

Author:

Robert Sedgewick, Kevin Wayne

Method Summary

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.

Methods inherited from class Object

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

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:

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

Parameters:

args - the command-line arguments