《算法4第一章》笔记（四）3-sum(1)

问题说明：

从一组数据中找出所有和为0的整数对的数量。(所有整数均各不相同)

源码：

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;

public class ThreeSum {
    public static int count(int[] a) {
        int N = a.length;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    if (a[i] + a[j] + a[k] == 0) {
                        cnt++;
                    }
                }
            }
        }
        return cnt;
    }
    public static void main(String[] args) {
        int[] a = new In(args[0]).readAllInts();
        StdOut.println(count(a));
    }
}

程序输入取自1Kints.text文件，内容为1000个带正负的随机整数

 324110
-442472
 626686
-157678
 508681
 123414
 -77867
 155091
 129801
 287381
 604242
 686904
-247109
  77867
 982455
-210707
-922943
-738817
  85168
 855430
-365580
-174307
 -28560
 888769
-887534
-563503
......

程序入口

public static void main(String[] args) {
    int[] a = (new In(args[0])).readAllInts();
    // 取得数据数组，调用count方法计数
    StdOut.println(count(a));
}

算法逻辑分析

public static int count(int[] a) {
        int N = a.length;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                        // 逐一运算，和为0则计数
                    if (a[i] + a[j] + a[k] == 0) {
                        cnt++;
                    }
                }
            }
        }
        return  cnt;
    }