在 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.

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

从列表 X 的第一个元素和列表 Y 的最后一个元素开始
检查它是否是迄今为止最好的一对（如果是，记住它）
如果该总和小于目标，则移至 X 的下一个较高元素。如果该总和大于目标，则移至 Y 的下一个较低元素
循环步骤 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步，仅存储目前最接近的非超出和的总和。

Answer 2

谢谢你的算法，我已经实现了我的逻辑。是的，它确实需要是低于目标的最接近的一对，所以我相应地对代码进行了更改。由于输入可能是重复的，因此我也确保了处理。结果也可能是多个，因此也可以处理。如果您发现任何潜在的优化，请告诉我。这是代码：

  public static List<List<Integer>> findClosest(int[] x, int[] y, int target){
         List<List<Integer>> result = new ArrayList<List<Integer>>();
         int[] pair = new int[2];
         int bestDiff = Integer.MIN_VALUE;
         int xIndex = 0;
         int yIndex = y.length - 1;
         //while left doesn't reach left end and right doesn't reach right end
         while(xIndex < x.length && yIndex >= 0){
             int xValue = x[xIndex];
             int yValue = y[yIndex];
             int diff = xValue + yValue - target;
             //values greater than target, y pointer go right
             if(diff > 0){
                 yIndex--;
                 while(yIndex > 0 && yValue == y[yIndex - 1]) yIndex--;
             }else{//combined == 0 which match target and < 0 which means the sum is less than target
                 //duplicates result, just add
                 if(diff == bestDiff){
                     result.add(Arrays.asList(xValue, yValue));
                 }
                 //found better pair, clear array and add new pair
                 else if(diff > bestDiff){
                     result.clear();
                     result.add(Arrays.asList(xValue, yValue));
                     bestDiff = diff;
                 }
                 xIndex++;
             }
         }
         return result;
  }

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

find the value pair in 2 sorted arrays (1 value from each array) where the sum is closest to a target value

java

arrays

optimization

dynamic-programming

closest