找到具有给定约束的最大和的对

Question

最近在一次工作面试中，我被要求在给定约束条件下求两个数组的最大和。这个问题措辞不同，但归结起来就是我上面所说的。没有提到元素是不同的，或者数组是被排序的。

例子：

A = [2000, 3000, 4000, 5000]
B = [6000, 5000, 4000, 1000]
Constraint: A[i] + B[j] <= 7000
Expected Result: (A[0], B[1]), (A[1], B[2])

请注意，由于约束，这与在2个数组中查找第k个最大和的对不同。

一个蛮力解是取2个数组的笛卡尔积，计算每对的和，过滤掉大于7000的，排序，取相等的顶值，时间复杂度为O（n²），我们能做的更好吗？

Answer 1

回答我自己的问题，以下是一个可行的解决方案：

public List<Map.Entry> max(int[] a, int[] b, int sum) {
    NavigableMap<Integer, Integer> distMap = new TreeMap<>();
    SortedMap<Integer, List<Map.Entry>> indicesMap = new TreeMap<>();

    for (int i = 0; i < a.length; i++) {
        distMap.put(a[i], i);
    }

    for (int i = 0; i < b.length; i++) {
        int diff = sum - b[i];
        Map.Entry<Integer, Integer> floorEntry = distMap.floorEntry(diff);
        if (Objects.nonNull(floorEntry)) {
            int tmp = b[i] + floorEntry.getKey();
            int j = i;
            indicesMap.merge(
                    tmp,
                    new ArrayList<Map.Entry>() {{
                        add(new AbstractMap.SimpleImmutableEntry<>(floorEntry.getValue(), j));
                    }},
                    (l1, l2) -> {
                        l1.addAll(l2);
                        return l1;
                    }
            );
        }
    }
    return indicesMap.get(indicesMap.lastKey());
}

时间复杂度：O（n） 表示 put O（nlogn） 表示 floorEntry，总体 O（nlogn）。空间复杂度 O（n）。

Answer 2

首先，您应该对两个数组进行排序。然后您可以使用此迭代：

for every number in A:
    perform binary search to find biggest element in B lower than 7000-A

您在二分搜索法找到的数字是数组A中当前数字的最佳配对数字。您可以取这些值的最大值(对于数组A的所有迭代)。

二进制搜索在O（logN）时间内运行，因此此迭代在O（NlogN）时间内运行，排序也在O（NlogN）时间内运行。您可以使用变量更改7000。