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}