算法练习(67): 4-sum(1.4.14)

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

• 4-sum问题

题目

1.4.14 4-sum。为 4-sum 设计一个算法。

---

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) { // 数组必须是有序的
        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;
    }

但显而易见，这个时间复杂度不行。我们看它的数量级，首先，它套了3层循环，这个复杂度是N³，然后每个if里都要二分法搜索，用了lgN。所以数量级是N³lgN,不是个好的解决方案。
然后我们详细分析一下，其实4Sum是Leecode中一个经典的问题。不信我们可以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

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。