本系列博客習(xí)題來自《算法(第四版)》，算是本人的讀書筆記记盒，如果有人在讀這本書的，歡迎大家多多交流外傅。為了方便討論纪吮，本人新建了一個微信群(算法交流)，想要加入的萎胰，請?zhí)砑游业奈⑿盘枺簔hujinhui207407 謝謝碾盟。另外，本人的個人博客 http://www.kyson.cn 也在不停的更新中技竟，歡迎一起討論

算法(第4版)

知識點

• 4-sum問題

題目

1.4.14 4-sum冰肴。為 4-sum 設(shè)計一個算法。

1.4.14 4-sum. Develop an algorithm for the 4-sum problem.

分析

稍加思考榔组，我們就能寫出如下的代碼

public int count(long[] a) {
        int cnt = 0;
        for (int i = 0; i < a.length - 1; i++)
            for (int j = i + 1; j < a.length - 1; j++)
                for (int k = j + 1; k < a.length - 1; k++)
                    if (rank(-a[i] - a[j] - a[k], a) != -1)
                        cnt++;
        return cnt;

    }

    public static int rank(long key, long[] a) { // 數(shù)組必須是有序的
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi) { // 被查找的鍵要么不存在熙尉，要么必然存在于a[lo..hi]之中
            int mid = lo + (hi - lo) / 2;
            if (key < a[mid])
                hi = mid - 1;
            else if (key > a[mid])
                lo = mid + 1;
            else
                return mid;
        }
        return -1;
    }

但顯而易見，這個時間復(fù)雜度不行搓扯。我們看它的數(shù)量級检痰，首先，它套了3層循環(huán)锨推，這個復(fù)雜度是N³铅歼，然后每個if里都要二分法搜索，用了lgN换可。所以數(shù)量級是N³lgN,不是個好的解決方案椎椰。
然后我們詳細(xì)分析一下，其實4Sum是Leecode中一個經(jīng)典的問題沾鳄。不信我們可以Google一下慨飘，可以看到很多的討論：
1.Quadratic algorithm for 4-SUM
2.LeetCode – 4Sum (Java)
3.4Sum Problem Analysis: O(N^2) VS O(N^2logN) VS O(N^3)
4.Time complexity analysis for the 3-sum/4-sum problem

答案

public int fourSum(int[] a) {
    int len = a.length;
    int cnt = 0;
    for (int l = 0; l < len - 3; l++) {
        for (int i = l + 1; i < len - 2; i++) {
            for (int j = i + 1, k = len - 1; j < k;) {
                if (a[l] + a[i] + a[j] + a[k] < 0) {
                    j++;
                } else if (a[l] + a[i] + a[j] + a[k] > 0) {
                    k--;
                } else {
                    cnt++;
                    j++;
                    k--;
                }
            }
        }
    }
    return cnt;
}

測試用例

public static void main(String[] args){
    String filePathString = System.getProperty("user.dir");
    String intFileString = filePathString
            + "/src/com/kyson/chapter1/section4/" + "1Kints.txt";
    
    In in = new In(intFileString);
    long[] a = in.readAllLongs();
    Arrays.sort(a);
    FourSum sum = new FourSum();
    StdOut.println(sum.fourSum(a) + "對");
}

代碼索引

FourSum.java

廣告

我的首款個人開發(fā)的APP壁紙寶貝上線了，歡迎大家下載译荞。