edu.princeton.cs.algorithms

Class ThreeSum

java.lang.Object

edu.princeton.cs.algorithms.ThreeSum

public class ThreeSum
extends Object

The ThreeSum class provides static methods for counting and printing the number of triples in an array of integers that sum to 0 (ignoring integer overflow).

This implementation uses a triply nested loop and takes proportional to N^3, 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

Constructor Summary

Constructors

Constructor and Description
ThreeSum()

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

ThreeSum

public ThreeSum()

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

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