``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 ``` ```package algs14; import stdlib.*; /* *********************************************************************** * Compilation: javac ThreeSum.java * Execution: java ThreeSum input.txt * Data files: http://algs4.cs.princeton.edu/14analysis/1Kints.txt * http://algs4.cs.princeton.edu/14analysis/2Kints.txt * http://algs4.cs.princeton.edu/14analysis/4Kints.txt * http://algs4.cs.princeton.edu/14analysis/8Kints.txt * http://algs4.cs.princeton.edu/14analysis/16Kints.txt * http://algs4.cs.princeton.edu/14analysis/32Kints.txt * http://algs4.cs.princeton.edu/14analysis/1Mints.txt * * A program with cubic running time. Read in N integers * and counts the number of triples that sum to exactly 0 * (ignoring integer overflow). * * % java ThreeSum 1Kints.txt * 70 * * % java ThreeSum 2Kints.txt * 528 * * % java ThreeSum 4Kints.txt * 4039 * *************************************************************************/ public class ThreeSum { public static int ops; // print distinct triples (i, j, k) such that a[i] + a[j] + a[k] = 0 public static void printAll(int[] a) { int N = a.length; for (int i = 0; i < N; i++) { for (int j = i+1; j < N; j++) { for (int k = j+1; k < N; k++) { if (a[i] + a[j] + a[k] == 0) { StdOut.println(a[i] + " " + a[j] + " " + a[k]); } } } } } // return number of distinct triples (i, j, k) such that a[i] + a[j] + a[k] = 0 public static int count(int[] a) { int N = a.length; int cnt = 0; ops = 0; for (int i = 0; i < N; i++) { for (int j = i+1; j < N; j++) { for (int k = j+1; k < N; k++) { ops += 3; if (a[i] + a[j] + a[k] == 0) { cnt++; } } } } return cnt; } public static void main(String[] args) { args = new String[] { "data/100ints.txt" }; // args = new String[] { "data/200ints.txt" }; // args = new String[] { "data/500ints.txt" }; // args = new String[] { "data/1Kints.txt" }; // args = new String[] { "data/2Kints.txt" }; // args = new String[] { "data/4Kints.txt" }; // args = new String[] { "data/8Kints.txt" }; int[] a = new In(args[0]).readAllInts(); //printAll (a); Stopwatch timer = new Stopwatch(); int cnt = count(a); StdOut.println("elapsed time = " + timer.elapsedTime()); StdOut.println(cnt); } } ```