在数组中查找一对数字，使它们的和等于给定的值

Question

在数组中查找一对数字，使它们的和等于给定的值

arraysperformancealgorithmprocessing-efficiency

35

问题: 给定一个无序的正整数数组，是否可能从该数组中找到一对整数，使它们的和等于给定的总和?

约束条件: 该算法应该在O(n)的时间复杂度内原地完成(不使用任何外部存储器，如数组、哈希映射等) (您可以使用额外的变量/指针)

如果这不可能，是否可以给出证明?

- noMAD

我只能想到一种使用外部数组的方法。我认为在O(n)时间内不可能实现。 - Jakob Weisblat

8

@RomanB.：这不是我的作业。我正在为面试学习，这只是突然想到的一个问题。 - noMAD

相关但不同：设计一个算法来查找数组中所有相加得到指定值的整数对？ - PengOne

在假设您有n个可以读取内存的处理器的情况下，生成n个线程以在O(n)时间内进行搜索是否不可行？ :) - corsiKa

我有一个O(n)的原地算法，如下所示。 - Paul Hankin

显示剩余5条评论

20个回答

12

一个在已排序数组上的时间复杂度为O(N)，空间复杂度为O(1)的解决方案：

设M是你想要的值。使用两个指针X和Y。将X=0置于开头，将Y=N-1置于末尾。计算和sum = array[X] + array[Y]。如果sum>M，则将Y减少；否则将X增加。如果这两个指针相交，则没有解。

你可以原地排序来处理一般数组，但我不确定是否有一般情况下时间复杂度为O(N)、空间复杂度为O(1)的解决方案。

- PengOne

1

如果我们知道数组元素的上限，可以使用基数排序或计数排序（O(n)），并应用您所述的算法。 - niting112

5

以下是我的Java解决方案（时间复杂度为O(n)），它将输出所有给定和的配对

import java.util.HashMap;
import java.util.Map;

public class Test {
public static void main(String[] args) {
    // TODO Auto-generated method stub
    Map<Integer, Integer> hash = new HashMap<>();
    int arr[] = {1,4,2,6,3,8,2,9};
    int sum = 5;
    for (int i = 0; i < arr.length; i++) {
        hash.put(arr[i],i);
    }
    
    for (int i = 0; i < arr.length; i++) {
        if(hash.containsKey(sum-arr[i])){
            //System.out.println(i+ " " +  hash.get(sum-arr[i]));
             System.out.println(arr[i]+ " " + (sum-arr[i]));
        }
    }
}
}

- Chetan Kole

打印语句应该是 "System.out.println(arr[i]+ " " + (sum-arr[i]));"。 - user2001627

3

正如 @PengOne 所提到的，通常情况下是不可能的。但是如果对输入数据做一些限制。

所有元素都是 + 或者 -，如果不是，则需要知道范围（高，低）并进行更改。
K，两个整数之和与一般元素相比是稀疏的。
可以破坏 i/p 数组 A[N]。

第1步：将所有小于SUM的元素移动到数组的开头，在N次操作中，我们将数组划分为[0，K]和[K，N-1]，使得[0，K]包含元素<= SUM。

第2步：由于我们知道范围（0到SUM），因此我们可以使用基数排序。

第3步：在A[K]上使用二分查找，好处之一是，如果我们需要查找补充元素，则仅需要查看A[K]的一半。因此，在A[k]中，我们迭代 A [0 to K / 2 + 1]，需要在A[i to K]中进行二进制搜索。

因此，总时间约为 N + K + K/2 lg (K)，其中 K 是输入 A[N] 中 0 到 Sum 之间的元素数量。

注意：如果您使用 @PengOne 的方法，则可以在K步骤中完成步骤3。因此，总时间将为 N+2K，这绝对是 O(N)。

我们不使用任何额外的内存，但会破坏输入数组，但由于开始时它没有任何排序，因此这也不是什么问题。

- d1val

3

如果数组中包含数字，且你事先知道其上限，则可以使用计数排序或基数排序（O(n)）并使用@PengOne建议的算法来实现。

否则，我想不出O(n)解决方案。但是，O(nlgn)解决方案可以这样实现：

首先使用归并排序或快速排序（用于原地排序）对数组进行排序。查找是否在排序后的数组中存在sum - array_element。可以使用二分搜索进行查找。

So total time complexity: O(nlgn) + O(lgn) -> O(nlgn).

- niting112

2

以下网站提供了一个简单的解决方案，使用哈希集合查找给定和减去当前数字的数值： http://www.dsalgo.com/UnsortedTwoSumToK.php

- partha pratim sirker

2

这是一个O(N)的算法，它依赖于一个原地O(N)去重算法和一个适用于数组中整数的好哈希函数。

首先，从数组中删除所有重复项。

其次，遍历数组，并将每个数字x替换为min(x, S-x)，其中S是您想要达到的总和。

第三，查找数组中是否有任何重复项：如果“x”被重复，则“x”和“S-x”必须在原始数组中出现，那么您就找到了您的一对。

- Paul Hankin

2

首先，使用基数排序对数组进行排序。这将花费O(kN)的时间。然后按照@PengOne的建议继续操作。

- Miquel

2

在JavaScript中：当n大于时间并且迭代次数增加时，此代码将执行。程序所执行的测试次数将等于((n*(n/2)+n/2)，其中n是元素的数量。在if（arr[i] + arr[j] === 0）中，给定的和数会被丢弃，其中0可以是任何给定的数字。

var arr = [-4, -3, 3, 4];          
                var lengtharr = arr.length;        
                var i = 0;                         
                var j = 1;                         
                var k = 1;                          
                do {                                                    
                    do {
                        if (arr[i] + arr[j] === 0) { document.write(' Elements arr [' + i + '] [' + j + '] sum 0'); } else { document.write('____'); }
                     j++;
                    } while (j < lengtharr);        
                    k++;
                    j = k;
                    i++;
                } while (i < (lengtharr-1));

- EJISRHA

2

Use count sort to sort the array O(n).
take two pointers one starts from 0th index of array, and another from end of array say (n-1).

run the loop until low <= high
```
Sum = arr[low] + arr[high]  
if(sum == target)
       print low, high
if(sum < target)
       low++
if(sum > target)
       high--
```
Step 2 to 10 takes O(n) time, and counting sort takes O(n). So total time complexity will be O(n).

- Jay

计数排序的时间复杂度是O(n)？？..哇！！ - Anil

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hugomg · Accepted Answer

如果你有一个已排序的数组，你可以通过将两个指针向中间移动，在O(n)时间内找到这样一对元素。

i = 0
j = n-1
while(i < j){
   if      (a[i] + a[j] == target) return (i, j);
   else if (a[i] + a[j] <  target) i += 1;
   else if (a[i] + a[j] >  target) j -= 1;
}
return NOT_FOUND;

如果你对数字的大小有限制（或者数组一开始就是有序的），那么排序可以做到O(N)。即使如此，log n因子很小，我不想费心去刨掉它。

证明：

如果存在解(i*, j*)，假设无失一般性，i在j到达j*之前到达了i*。由于对于在j*和j之间的所有j'，我们知道a[j'] > a[j*]，因此我们可以推断出a[i] + a[j']>a[i*]+a[j*]=目标，因此算法的后续步骤将导致j减少直到到达j*(或相等的值)，而不给i向前推进并“错过”解决方案的机会。对反方向的解释是类似的。