本系列博客習(xí)題來自《算法(第四版)》，算是本人的讀書筆記，如果有人在讀這本書的，歡迎大家多多交流。為了方便討論，本人新建了一個(gè)微信群(算法交流)，想要加入的，請?zhí)砑游业奈⑿盘?hào)：zhujinhui207407 謝謝。另外，本人的個(gè)人博客 http://www.kyson.cn 也在不停的更新中，歡迎一起討論

算法(第4版)

知識(shí)點(diǎn)

• 4-sum問題

題目

1.4.14 4-sum。為 4-sum 設(shè)計(jì)一個(gè)算法。

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;
    }

但顯而易見，這個(gè)時(shí)間復(fù)雜度不行。我們看它的數(shù)量級(jí)，首先，它套了3層循環(huán)，這個(gè)復(fù)雜度是N³，然后每個(gè)if里都要二分法搜索，用了lgN。所以數(shù)量級(jí)是N³lgN,不是個(gè)好的解決方案。
然后我們詳細(xì)分析一下，其實(shí)4Sum是Leecode中一個(gè)經(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

廣告

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