java - 在 2 个排序数组(每个数组中有 1 个值)中找到值对，其中总和最接近目标值

Question

原始问题有一个未排序的 2 个整数列表。为了简化这个问题，我们只考虑输入是 2 个排序的整数数组和一个整数目标。如果有超过 1 个解决方案对，值对可以重复。

例如:[7,8,14],[5,10,14] 目标:20解决方案是 [14, 5]，因为第一个数组中的 14 和第二个数组中的 5 总和为 19，最接近 20。

我的解决方案是从头到尾循环遍历两个数组，并与跟踪的最小差异进行比较，如果新差异更小，则进行更新。

但这是蛮力。有没有更好的解决方案？

我在网上找到的大多数解决方案都是从同一个数组中找到目标，2个数组目标问题和1个数组之间有什么相似之处吗？

Answer 1

一个关键见解:给定一对 (x, y)，其总和高于目标值，该总和比任何对 (x, y') 的总和更接近，其中 y' > y。相反，如果 (x, y) 的总和低于目标，则该总和比任何对 (x', y) 的总和更接近，其中 x' < x。

这会在线性时间内产生一个算法:

1. 开始列表X的第一个元素和列表Y的最后一个元素
2. 检查它是否是迄今为止最好的一对(如果是，记住它)
3. 如果该总和小于目标值，则移至 X 的下一个较高元素。如果该总和大于目标值，则移至 Y 的下一个较低元素
4. 循环步骤 2 - 3，直到用完 X 或 Y 中的元素

在 Java 中:

private static Pair<Integer, Integer> findClosestSum(List<Integer> X, List<Integer> Y, int target) {
    double bestDifference = Integer.MAX_VALUE;
    Pair<Integer, Integer> bestPair = null;
    int xIndex = 0;
    int yIndex = Y.size() - 1;

    while (true) {
        double sum = X.get(xIndex) + Y.get(yIndex);
        double difference = Math.abs(sum - target);
        if (difference < bestDifference) {
            bestPair = new Pair<>(X.get(xIndex), Y.get(yIndex));
            bestDifference = difference;
        }

        if (sum > target) {
            yIndex -= 1;
            if (yIndex < 0) {
                return bestPair;
            }
        } else if (sum < target) {
            xIndex += 1;
            if (xIndex == X.size()) {
                return bestPair;
            }
        } else {
            // Perfect match :)
            return bestPair;
        }
    }
}

您可以通过开头段落中的逻辑证明此算法是详尽无遗的。对于任何没有访问过的对，必须有一个对包括它的两个被访问过的元素之一，并且其总和严格接近目标。

编辑:如果您只想要小于目标的总和(而不是超出目标的总和)，则相同的逻辑仍然适用。在超调的情况下，(x, y') 与 (x, y) 一样无效，因此它不是更好的候选和。在这种情况下，只需要修改第 2 步，仅存储目前为止最接近的非超出和的和。