001package algs14;
002import stdlib.*;
003import java.util.Arrays;
004/* ***********************************************************************
005 *  Compilation:  javac ThreeSumFast.java
006 *  Execution:    java ThreeSumFast input.txt
007 *  Data files:   http://algs4.cs.princeton.edu/14analysis/1Kints.txt
008 *                http://algs4.cs.princeton.edu/14analysis/2Kints.txt
009 *                http://algs4.cs.princeton.edu/14analysis/4Kints.txt
010 *                http://algs4.cs.princeton.edu/14analysis/8Kints.txt
011 *                http://algs4.cs.princeton.edu/14analysis/16Kints.txt
012 *                http://algs4.cs.princeton.edu/14analysis/32Kints.txt
013 *                http://algs4.cs.princeton.edu/14analysis/1Mints.txt
014 *
015 *  A program with N^2 log N running time. Read in N integers
016 *  and counts the number of triples that sum to exactly 0.
017 *
018 *  Limitations
019 *  -----------
020 *     - we ignore integer overflow
021 *     - doesn't handle case when input has duplicates
022 *
023 *
024 *  % java ThreeSumFast 1Kints.txt
025 *  70
026 *
027 *  % java ThreeSumFast 2Kints.txt
028 *  528
029 *
030 *  % java ThreeSumFast 4Kints.txt
031 *  4039
032 *
033 *  % java ThreeSumFast 8Kints.txt
034 *  32074
035 *
036 *  % java ThreeSumFast 16Kints.txt
037 *  255181
038 *
039 *  % java ThreeSumFast 32Kints.txt
040 *  2052358
041 *
042 *************************************************************************/
043
044public class ThreeSumFast {
045
046        // print distinct triples (i, j, k) such that a[i] + a[j] + a[k] = 0
047        public static void printAll(int[] a) {
048                int N = a.length;
049                Arrays.sort(a);
050                for (int i = 0; i < N; i++) {
051                        for (int j = i+1; j < N; j++) {
052                                int k = Arrays.binarySearch(a, -(a[i] + a[j]));
053                                if (k > j) StdOut.println(a[i] + " " + a[j] + " " + a[k]);
054                        }
055                }
056        }
057
058        // return number of distinct triples (i, j, k) such that a[i] + a[j] + a[k] = 0
059        public static int count(int[] a) {
060                int N = a.length;
061                Arrays.sort(a);
062                int cnt = 0;
063                for (int i = 0; i < N; i++) {
064                        for (int j = i+1; j < N; j++) {
065                                int k = Arrays.binarySearch(a, -(a[i] + a[j]));
066                                if (k > j) cnt++;
067                        }
068                }
069                return cnt;
070        }
071
072        public static void main(String[] args)  {
073                //args = new String[] { "data/2Kints.txt" };
074
075                int[] a = new In(args[0]).readAllInts();
076                int cnt = count(a);
077                StdOut.println(cnt);
078        }
079}