java - 使得元素之和小于或等于 k ​​的方式总数

Question

任务:找到从每个数组中挑选单个元素的可能方法的数量，使得它们的总和小于 k。

这是我的程序:

public static long process(List<Integer> a, List<Integer> b, List<Integer> c, List<Integer> d, int k) {
    Collections.sort(a);
    Collections.sort(b);
    Collections.sort(c);
    Collections.sort(d);
    long total = 0;
    // four layer for loop to check all combinations of four arrays
    for (int i = 0; i < a.size(); i++) {
        long v = a.get(i);
        for (int j = 0; j < b.size() && v < k; j++) {
            long v1 = b.get(j);
            for (int m = 0; m < c.size() && v + v1 < k; m++) {
                long v2 = c.get(m);
                for (int l = 0; l < d.size() && v + v1 + v2 < k; l++) {
                    long v3 = d.get(l);
                    if (v + v1 + v2 + v3 <= k) {
                        total = total + 1;
                    } else {
                        break;
                    }
                }
            }
        }
    }
    return total;   
}

这是在面试中被问到的，我看到当我使用它时，程序因测试用例而失败，说超过了时间限制。

执行此任务的最佳方法是什么？

Answer 1

令列表的长度为N .你的方法是O(N^4) ，这很可能会超时。
一个简单但更快的方法是:

1. 从数组 k 生成所有对和(小于 A )和 B .将它们存储在数组中 X .复杂度:O(N^2)
2. 从数组 k 生成所有对和(小于 C )和 D ，将它们存储在数组 Y 中.复杂度:O(N^2)
3. 排序数组 X和 Y .复杂性:O(N^2 logN)
4. 对于 X 中的每个元素，找到Y中的最大元素这样他们的sum < k .使用二分查找，复杂度:O(N^2 logN)

空间复杂度:O(N^2) ，时间复杂度:O(N^2 logN)