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