ThreeSum问题

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=i+1; j<N; j++)
                for(int k=j+1; k<N; k++)
                    if(a[i] + a[j] + a[k] == 0)
                        cnt++;
        return cnt;
    }
    public static void main(String[] args){
        int[] a=In.readInts(args[0]);
        StdOut.println(count(a));
    }
}

ThreeSum问题：计算所有不同的整数的三元组的和，统计和为0的数量。上述代码是最简单直接的求解方式。

通过简单的改进，我们可以很容易实现更优的算法——利用归并排序和二分查找。
首先简化问题，不妨考虑TwoSum问题：
TwoSum问题也可以很容易实现平方级别的解决——通过双层循环来暴力求解，但通过归并排序和二分查找，我们将在线性对数级别解决TwoSum问题：

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.rank(-a[i], a) > i)
                cnt++;
        return cnt;
    }
    public static void main(String[] args){
    int[] a = In.readInts(args[0]);
    StdOut.println(count(a));
    }
}

改进后的算法思想是当且仅当-a[i]存在于数组中(且a[i]非零)时，a[i]存在于某个和为零的整数对之中。我们首先将数组排序，然后对于数组中的每个a[i]，使用BinarySearch的rank()方法对-a[i]进行二分查找。
归并排序所需的时间与NlogN成正比，二分查找所需的时间与logN成正比，所以总时间与NlogN成正比。
这种方式对于3-sum问题同样有效，当且仅当-(a[i]+a[j])存在于数组中时，整数对a[i]和a[j]是某个和为零的三元数组的一部分。

import java.util.Arrays;
public class ThreeSumFast{
    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 = i+1; j < N; j++)
                if(BinarySearch.rank(-a[i]-a[j],a) > j)
                    cnt++;
        return cnt;
    }
    public static void main(String[] args){
          int[] a = In.readInts(args[0]);
          StdOut.println(count(a));
    }
}

每次查找的时间与logN成正比，所以总运行时间与N²logN成正比。