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

ThreeSum問題:すべての異なる整数の三元グループの和を計算し、統計し、0の数にする.上記のコードは最も簡単で直接的な解法である.
簡単な改良により,より優れたアルゴリズムを容易に実現でき,集計ソートと二分検索を利用することができる.まず問題を簡略化し、TwoSum問題を考慮してみてください.TwoSum問題も2乗レベルの解決を容易に実現することができます.2層サイクルで暴力的に解くことができますが、集計ソートと2点検索を通じて、線形対数レベルで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が比例する.