在特定条件下从给定整数中查找总和达到目标值的所有对的最有效方法

Question

我正在寻找一种有效的方法来打印大量整数中的对，这些整数在某些条件下总和达到目标值：

• 第一个 int 应该小于第二个 int 对
• 打印应按该对中的第一个升序

我编写了一些意大利面条代码，它们在时间复杂度上似乎比两个循环更有效，但是，它不包括排序。我目前已经没有想法了。

我的问题如下：

1. 对输出进行排序的最佳方法是什么？
2. 除了我当前的解决方案之外，还有其他方法可以提高时间复杂度吗？

输出可能很大，所以我想知道是否应该替换System.out.println().

我必须打印出所有的配对。一个 int 可以有很多对。输入最多可以增长到数十万个整数。

给定目标 12：
示例输入：
2 10 0 8 4 12 8

输出示例：
0 12
2 10
4 8
4 8

public static void myFindPair(int[] arr, int target) {

    // Key = difference, value = index
    Map<Integer, Integer> map = new HashMap();

    for (int i = 0; i < arr.length; i++) {
        int difference = target - arr[i];
        map.put(difference, i);
        System.out.print(arr[i]);
    }

    for (int i = 0; i < arr.length; i++) {
        if (map.containsKey(arr[i]) && map.get(arr[i]) != i) {
            int first = arr[i];
            int second = arr[map.get(arr[i])];
            if (first < second) {
                System.out.println(first + " " + second);
            }
        }
    }
}

Answer 1

首先对数组进行排序。如果arr和 已排序arr[0] + arr[arr.length - 1] > target，则arr[arr.length - 1]不可能成对；您将其添加到尽可能小的值，但它对于目标来说仍然太大。类似地， if arr[0] + arr[arr.length] < target, thenarr[0]不可能是一对的一部分。这导致了以下算法。

public /* return type */ findPair(int[] arr, int target)
{
  Arrays.sort(arr);

  int i = 0, j = arr.length - 1;
  
  while (i < j) {
    int sum = arr[i] + arr[j];
    if (sum < target) i++;
    else if (sum > target) j--;
    else {
      /* sum == target, so add arr[i] and arr[j] to a set of solutions. */
      /* I'm assuming that the elements of arr are unique. */
      i++;
      j--;
    }
  }

  return /* set of solutions */
}