找到所有相加等于 S 的数字对。

Question

给定一个数组，找到所有相加等于给定值的数对。

有一个经典的O(n)算法是将两个指针放在数组的前后两端，逐渐向中间移动以找到该数对。但这种方法只能找到一个数对。如果你想找到所有的数对怎么办呢?

Bonus: 找到距离最小的数对。

你可以用O(n)的时间复杂度来解决这个问题吗？

- shreyasva

---

我认为这个“经典”算法需要对列表进行排序才能工作。如果是这样，那么找到所有的配对并不难。 - drysdam

数组是否已排序？如果是，则前后指针算法将在O(n)时间内为您提供所有满意的配对，最后产生的配对将具有最小距离的元素对。 - Henry

是的，它已经排序了。你能解释一下吗？ - shreyasva

好的，下面是我的翻译尝试：让我们先看看你的尝试。 - drysdam

可以通过说“不”的骑士成对地产生数字对。 - Svante

Answer 1

 int arr[SIZE]; /* sorted in ascending order */

 int a = 0, b = SIZE - 1, mindist = -1, sum;
 while (a < b) {
    sum = arr[a] + arr[b];
    if (sum == TARGET) { report_pair(a, b); mindist = b - a; a++ }
    else if (sum < TARGET) a++;
    else b--;
 }

 /* minimum distance stored in mindist */

- Antti Huima

---

对于 TARET = 10，且 a[]={5,5,5,5,5} 的情况下，它输出的答案是 4 而不是 10。 - pranay

Answer 2

一种简单且高效的解决方案是使用整数到整数的哈希表。该算法通过迭代整个数组来实现。对于每个元素x，查找哈希表中的sum-x，并且如果存在，则打印(x，sum-x)。将x添加到哈希表中，然后继续下一个元素。

但是针对已排序的数组，若想达到O(1)常数空间和O(n)线性时间，则以下代码肯定可行。

public static void printPairSums(int[] array, int sum) {
    Arrays.sort(array);
    int first = 0;
    int last = array.length - 1;
    while (first < last) {
        int s = array[first] + array[last];
        if (s == sum) {
            System.out.println(array[first] + “ “ + array[last]);
            ++first;
            --last;
        } else {
            if (s < sum) ++first;
            else --last;
        }
    }
 }

- coder_15

Answer 3

public static void main(String[] args) {
        int[] nums = new int[] { 1,2,3,4,5,6,7,8,9};
        Hashtable  reqNoList=new Hashtable();
        int sum=6;
        int minPair=0,i=0,count=0;
        // just remove the second condition for unsorted array
        while(i<nums.length && i<sum){
            int key=sum-nums[i];
            if(reqNoList.containsKey(nums[i])){
                Integer temp=(Integer) reqNoList.get(nums[i]);
                System.out.println("("+key+","+nums[i]+")");
                if(count==0)
                    minPair=i-temp;
                else if((i-temp)< minPair)
                    minPair=i-temp;
                count++;
            }else
                reqNoList.put(key,i);
            i++;
        }
        System.out.println("min Distance -->"+minPair);
    }

- Gopal

Answer 4

源代码 链接

位向量：

我喜欢这个。使用大小等于总和的位向量（即位数组）。

1.clear all bits
2.for each element a[i] in the array
  - if bit sum-a[i] is set, return sum-a[i], a[i]
  - else, set bit a[i]

这将需要常数存储O(n)，而时间复杂度在任何情况下都是O(n)。

- rishi

---

常量存储，但该常量是每个可能的整数的一位。需要五亿字节来处理半打整数的算法可能不是理想的选择... - Nick Barnes

如果我让你感到困惑，我很抱歉。我的意思是每个整数使用一个比特位来表示，第n个整数将由第n个比特位表示。也就是说，如果我们有五亿个整数，我们只需要五亿个比特位。 - rishi

存储是O(n)。我在上句话中搞错了。纠正一下，但我不确定为什么您需要O(logN)来检查位sum-a[i]。对我来说，位向量类似于布尔数组，只是使用一个比特的存储空间而不是一个字节。因此，假设获取 bitVector[sum-a[i]] 应该是O(1)。 - rishi

假设 sum 为 4,000,000,000，a[] 为 {4,5,6}。在第一次迭代中，您需要检查 bitVector[3999999996]。如果您没有存储 2^32 位，那么如何以 O(1) 的时间复杂度进行此查找？ - Nick Barnes

不仅在总和不可能时才需要考虑; 考虑 sum=4000000000，a={1,3999999999}。无论如何，真正的问题是您事先不知道需要检查哪些位。当您初始化您的 bitVector 时，即使 sum=3，a={1,2}，您仍然需要创建第4000000000个位。 - Nick Barnes

Answer 5

对coder_15的回答进行小修改，以检查第一个元素的下一个元素是否与第一个元素相同或最后一个元素的前一个元素是否与最后一个元素相同：

while(first<last){
    int s = arr[first] + arr[last];
    if(s == sum){
        System.out.println(arr[first] + " : " + arr[last]);
        if(arr[first] == arr[first+1] ){
            System.out.println(arr[first+1] + " : " + arr[last]);
        }
        if(arr[last] == arr[last-1] ){
            System.out.println(arr[first] + " : " + arr[last-1]);
        }
        ++first; 
        --last; 
    }

    else{
        if(s<sum){
            ++first; 
        }
        if(s>sum)
            --last;
    }
}

- Neetigya