arrays - 在数组中找到添加到给定总和的一对数字

Question

问题：给定一个未排序的正整数数组，是否有可能从该数组中找到一对整数求和？

约束：这应该在 O(n) 和就地完成（没有任何外部存储，如数组、哈希映射）（您可以使用额外的变量/指针）

如果这是不可能的，是否可以提供相同的证据？

score 55 · 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到达i*之前j到达j*。因为我们知道我们可以推断出这一点j'，j*因此，算法的所有后续步骤将导致 j 减小直到它达到（或相等的值），而没有机会向前推进并“错过”解决方案。ja[j'] > a[j*]a[i] + a[j'] > a[i*] + a[j*] = targetj*i

另一个方向的解释类似。

score 12 · Accepted Answer

适用于排序数组的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)空间解决方案。

score 5 · Accepted Answer

我在 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]));
        }
    }
}
}

score 3 · Accepted Answer

如果数组包含数字，这可能是可能的，您事先知道其上限。然后使用计数排序或基数排序（o（n））并使用@PengOne建议的算法。

否则我想不出 O(n) 解决方案。但是 O(nlgn) 解决方案以这种方式工作：-

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

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

score 3 · Accepted Answer

正如@PengOne 提到的，这在一般情况下是不可能的。但是如果你对 i/p 数据做一些限制的话。

所有元素都是 + 或全部 -，如果不是，则需要知道范围（高、低）并进行更改。
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 到 K/2 + 1] 我们需要在 A[i 到 K] 中进行二分查找。

所以总appx。时间是，N + K + K/2 lg (K) 其中 K 是 i/p A[N] 中从 0 到 Sum 的元素数量

注意：如果您使用@PengOne 的方法，您可以在 K 中执行 step3。所以总时间将是 N+2K，这绝对是 O(N)

我们不使用任何额外的内存，但破坏了 i/p 数组，这也不错，因为它一开始没有任何排序。

score 2 · Accepted Answer

首先，使用radix sort对数组进行排序。这会让你回到 O(kN)。然后按照@PengOne 的建议进行。

score 2 · Accepted Answer

以下站点使用哈希集提供了一个简单的解决方案，该解决方案看到一个数字，然后在哈希集中搜索给定的总和当前数字 http://www.dsalgo.com/UnsortedTwoSumToK.php

score 2 · Accepted Answer

这是一个 O(N) 算法。它依赖于就地 O(N) 重复删除算法，以及数组中整数的良好哈希函数的存在。

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

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

第三，查找数组中是否有任何重复：如果“x”重复，则“x”和“Sx”一定出现在原始数组中，并且您已经找到了您的对。

score 2 · Accepted Answer

使用计数排序对数组 O(n) 进行排序。
取两个指针，一个从数组的第 0 个索引开始，另一个从数组的末尾说 (n-1)。

运行循环直到低 <= 高
```
Sum = arr[low] + arr[high]  
if(sum == target)
       print low, high
if(sum < target)
       low++
if(sum > target)
       high--
```
步骤 2 到 10 需要 O(n) 时间，计数排序需要 O(n)。所以总时间复杂度将是 O(n)。

score 2 · Accepted Answer

在 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));

score 1 · Accepted Answer

这是一个考虑到重复条目的解决方案。它是用 javascript 编写的，并使用已排序和未排序的数组运行。解决方案在 O(n) 时间内运行。

var count_pairs_unsorted = function(_arr,x) {
  // setup variables
  var asc_arr = [];
  var len = _arr.length;
  if(!x) x = 0;
  var pairs = 0;
  var i = -1;
  var k = len-1;
  if(len<2) return pairs;
  // tally all the like numbers into buckets
  while(i<k) {
    asc_arr[_arr[i]]=-(~(asc_arr[_arr[i]]));
    asc_arr[_arr[k]]=-(~(asc_arr[_arr[k]]));
    i++;
    k--;
  }
  // odd amount of elements
  if(i==k) {
    asc_arr[_arr[k]]=-(~(asc_arr[_arr[k]]));
    k--;
  }
  // count all the pairs reducing tallies as you go
  while(i<len||k>-1){
    var y;
    if(i<len){
      y = x-_arr[i];
      if(asc_arr[y]!=undefined&&(asc_arr[y]+asc_arr[_arr[i]])>1) {
        if(_arr[i]==y) {
          var comb = 1;
          while(--asc_arr[_arr[i]] > 0) {pairs+=(comb++);}
        } else pairs+=asc_arr[_arr[i]]*asc_arr[y];
        asc_arr[y] = 0;
        asc_arr[_arr[i]] = 0;
      }

    }
    if(k>-1) {
      y = x-_arr[k];
      if(asc_arr[y]!=undefined&&(asc_arr[y]+asc_arr[_arr[k]])>1) {
        if(_arr[k]==y) {
          var comb = 1;
          while(--asc_arr[_arr[k]] > 0) {pairs+=(comb++);}
        } else pairs+=asc_arr[_arr[k]]*asc_arr[y];
        asc_arr[y] = 0;
        asc_arr[_arr[k]] = 0;
      }

    }
    i++;
    k--;
  }
  return pairs;
}

从数组的两侧开始，慢慢地向内移动，计算每个数字被找到的次数。一旦你到达中点，所有的数字都会被计算出来，你现在可以前进两个指针，一边计算对数。

它只计算对，但可以返工

找到对
找到对 < x
找到对 > x

享受！

score 1 · Accepted Answer

红宝石实现

ar1 = [ 32, 44, 68, 54, 65, 43, 68, 46, 68, 56]
for i in 0..ar1.length-1
 t  = 100 - ar1[i]
  if ar1.include?(t)
    s= ar1.count(t)
    if s < 2
      print   s , " - " ,  t, " , " , ar1[i]  , " pair ", i, "\n"
    end
  end
end

score 0 · Accepted Answer

这是python中的一个解决方案：

a = [9, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 9, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 2, 8, 9, 2, 2, 8,
     9, 2, 15, 11, 21, 8, 9, 12, 2, 8, 9, 2, 15, 11, 21, 7, 9, 2, 23, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 12, 9, 2, 15, 11, 21, 8, 9, 2, 2,
     8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 7.12, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9,
     2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 0.87, 78]
i = 0
j = len(a) - 1
my_sum = 8
finded_numbers = ()
iterations = 0
while(OK):
    iterations += 1
    if (i < j):
        i += 1
    if (i == j):
        if (i == 0):
            OK = False
            break
        i = 0
        j -= 1
    if (a[i] + a[j] == my_sum):
        finded_numbers = (a[i], a[j]) 
        OK = False
print finded_numbers
print iterations

score 0 · Accepted Answer

我在一次采访中被问到同样的问题，这就是我想到的方案。还有一个改进要做，允许负数，但只需要修改索引。空间方面不好，但我相信这里的运行时间是 O(N)+O(N)+O(N 的子集) -> O(N)。我可能错了。

void find_sum(int *array_numbers, int x){
 int i, freq, n_numbers; 
 int array_freq[x+1]= {0}; // x + 1 as there could be 0’s as well
 if(array_numbers)
 {
  n_numbers = (int) sizeof(array_numbers);
  for(i=0; i<n_numbers;i++){ array_freq[array_numbers[i]]++; } //O(N) 
  for(i=0; i<n_numbers;i++) 
  { //O(N) 
   if ((array_freq[x-array_numbers[i]] > 0)&&(array_freq[array_numbers[i]] > 0)&&(array_numbers[i]!=(x/2)))
   { 
    freq = array_freq[x-array_numbers[i]] * array_freq[array_numbers[i]];
    printf(“-{%d,%d} %d times\n”,array_numbers[i],x-array_numbers[i],freq ); 
    // “-{3, 7} 6 times” if there’s 3 ‘7’s and 2 ‘3’s
    array_freq[array_numbers[i]]=0;
    array_freq[x-array_numbers[i]]=0; // doing this we don’t get them repeated
   }
  } // end loop
  if ((x%2)=0)
  {
   freq = array_freq[x/2];
   n_numbers=0;
   for(i=1; i<freq;i++)
   { //O([size-k subset])
    n_numbers+= (freq-i); 
   } 
   printf(“-{%d,%d} %d times\n”,x/2,x/2,n_numbers);
  }
  return;
 }else{
 return; // Incoming NULL array 
 printf(“nothing to do here, bad pointer\n”);
 }
}

欢迎批评。

score 0 · Accepted Answer

在 java 中，这取决于数组中的最大数量。它返回一个具有两个元素索引的 int[]。它开着）。

  public static int[] twoSum(final int[] nums, int target) {
    int[] r = new int[2];
    r[0] = -1;
    r[1] = -1;
    int[] vIndex = new int[0Xffff];
    for (int i = 0; i < nums.length; i++) {
        int delta = 0Xfff;
        int gapIndex = target - nums[i] + delta;
        if (vIndex[gapIndex] != 0) {
            r[0] = vIndex[gapIndex];
            r[1] = i + 1;
            return r;
        } else {
            vIndex[nums[i] + delta] = i + 1;
        }
    }
    return r;
}

score 0 · Accepted Answer

首先，您应该找到反向数组 => 总和减去实际数组，然后检查这些新数组中的任何元素是否存在于实际数组中。

const arr = [0, 1, 2, 6];

const sum = 8;

let isPairExist = arr
  .map(item => sum - item) // [8, 7, 6, 2];
  .find((item, index) => {
    arr.splice(0, 1); // an element should pair with another element
    return arr.find(x => x === item);
  })
  ? true : false;

console.log(isPairExist);

score 0 · Accepted Answer

使用 Hash Table 的 O(n) 内存，可以将具有 O(nxn) 性能的朴素双循环打印输出改进为线性 O(n) 性能，如下所示：

void TwoIntegersSum(int[] given, int sum)
{
    Hashtable ht = new Hashtable();
    for (int i = 0; i < given.Length; i++)
        if (ht.Contains(sum - given[i]))
            Console.WriteLine("{0} + {1}", given[i], sum - given[i]);
        else
            ht.Add(given[i], sum - given[i]);
    Console.Read();
}

score 0 · Accepted Answer

def pair_sum(arr,k):
    counter = 0
    lookup = set()
    for num in arr:
        if k-num in lookup:
            counter+=1
        else:
            lookup.add(num)
    return counter
    pass
pair_sum([1,3,2,2],4)

python中的解决方案

score -1 · Accepted Answer

不保证可能；如何选择给定的总和？

示例：未排序的整数数组

2, 6, 4, 8, 12, 10

给定总和：

??

arrays - 在数组中找到添加到给定总和的一对数字

19 回答 19

Related

Reference