найти пару значений в 2 отсортированных массивах (по 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, чтобы сохранить сумму только в том случае, если это ближайшая непревышающая сумма на данный момент.

Спасибо за ваш алгоритм, я реализовал свою логику. Да, это должна быть ближайшая пара ниже цели, поэтому я внес соответствующие изменения в код. Поскольку входные данные могут быть дубликатами, я также позаботился об этом. Также результат может быть множественным, поэтому он также обрабатывается. Дайте мне знать, если вы обнаружите какую-либо потенциальную оптимизацию. Вот код:

  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;
  }