ThreeSum.java

/* *****************************************************************************
 *  Name:    Alan Turing
 *  NetID:   aturing
 *  Precept: P00
 *
 *  Description:  Prints 'Hello, World' to the terminal window.
 *                By tradition, this is everyone's first program.
 *                Prof. Brian Kernighan initiated this tradition in 1974.
 *
 **************************************************************************** */

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;

public class ThreeSum {
    public static int binarySearch(int[] a, int key)
    {
        int lo = 0;
        int hi = a.length;
        while(lo <= hi)
        {
            int mid = lo + (hi - lo) / 2;
            if (key < a[mid]) hi = mid - 1;
            else if (key > a[mid]) lo = mid + 1;
            else return mid;
        }
        return -1;
    }
    public static int count(int[] a)
    {
        int N = a.length;
        int count = 0;
        for (int i = 0; i < N; i++)
        {
            for (int j = i + 1; j < N; j++)
            {
                int ret = binarySearch(a, -(a[i] + a[j]));
                if (ret != -1)
                {
                    count += 1;
                }
            }
        }
        return count;
    }
    public static void main(String[] args) {
        int [] a = In.readInts(args[0]);
        StdOut.println(count(a));

    }
}