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

问题说明：

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

这次使用二分查找来优化算法

源码：

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

public class ThreeSum {
    public static int count(int[] a) {
        Arrays.sort(a);
        int N = a.length;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (BinarySearch.indexOf(a, -a[i]-a[j]) < j) {
                    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) {
        // 先对数组进行排序
        Arrays.sort(a);
        int N = a.length;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                    指定i和j可变，则k值为0-i值-j值
                if (BinarySearch.indexOf(a, -a[i] - a[j]) < j) {
                    cnt++;
                }
            }
        }
        return  cnt;
    }