元素之和小于或等于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;   
}

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

对于此任务，最好的方法是什么？

- learner

---

如果我看到四层的for循环，那么超时限制就不足为奇了。在大多数情况下，超过两层的循环都是值得怀疑的。 - MC Emperor

你至少可以在进入下一个循环之前开始对值进行求和，如果已经太高就停止（这可能会有所帮助）。但是最好的方法是尽量减少循环次数。 - Jelumar

@JanezKuhar，我已经修复了。 - learner

Answer 1

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

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

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

- Abhinav Mathur