001package algs14; 002import stdlib.*; 003/* *********************************************************************** 004 * Compilation: javac TwoSum.java 005 * Execution: java TwoSum input.txt 006 * Dependencies: In.java Stopwatch.java 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 running time. Read in N integers 016 * and counts the number of pairs that sum to exactly 0. 017 * 018 * 019 * Limitations 020 * ----------- 021 * - we ignore integer overflow 022 * 023 * 024 * % java TwoSum 2Kints.txt 025 * 2 026 * 027 * % java TwoSum 1Kints.txt 028 * 1 029 * 030 * % java TwoSum 2Kints.txt 031 * 2 032 * 033 * % java TwoSum 4Kints.txt 034 * 3 035 * 036 * % java TwoSum 8Kints.txt 037 * 19 038 * 039 * % java TwoSum 16Kints.txt 040 * 66 041 * 042 * % java TwoSum 32Kints.txt 043 * 273 044 * 045 *************************************************************************/ 046 047public class XTwoSum { 048 049 // print distinct pairs (i, j) such that a[i] + a[j] = 0 050 public static void printAll(int[] a) { 051 int N = a.length; 052 for (int i = 0; i < N; i++) { 053 for (int j = i+1; j < N; j++) { 054 if (a[i] + a[j] == 0) { 055 StdOut.println(a[i] + " " + a[j]); 056 } 057 } 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 int cnt = 0; 065 for (int i = 0; i < N; i++) { 066 for (int j = i+1; j < N; j++) { 067 if (a[i] + a[j] == 0) { 068 cnt++; 069 } 070 } 071 } 072 return cnt; 073 } 074 075// public static void main(String[] args) { 076// args = new String[] { "data/2Kints.txt" }; 077// int[] a = new In(args[0]).readAllInts(); 078// Stopwatch timer = new Stopwatch(); 079// int cnt = count(a); 080// StdOut.println("elapsed time = " + timer.elapsedTime()); 081// StdOut.println(cnt); 082// } 083}