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

问题说明：

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

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

源码：

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

import java.util.Arrays;

public class TwoSumFast {
    public static int count(int[] a) {
        Arrays.sort(a);
        int N = a.length;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if (BinarySearch.indexOf(a, -a[i]) > i) {
                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++) {
        // 逐一取出外层元素，调用二分查找法查找该值的负数是否存在，存在即为和为0的项
        if (BinarySearch.indexOf(a, -a[i]) > i) {
            cnt++;
        }
    }
    return  cnt;
}