找到数组中的一对数字，添加到给定的总和

Question

问题：给定一个未分类的正整数数组，是否有可能从该数组中找到一对总和为给定总和的整数？

约束：这应该在O（n）和就地完成（不喜欢阵列的任何外部存储，哈希地图）（你可以使用额外的变量/指针）

如果这是不可能的，能否有相同的证据？

Answer 1

如果你有一个排序后的数组，你可以通过移动两个指针向中间

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）的这样的一对可以由O（N）。如果你有结合在数字的大小（或者如果数组已经排序在第一位）。即使如此，log n因素非常小，我不想费心去刮。

证明：

如果有一个解决方案(i*, j*)，假设，不失一般性，即i达到i*之前j达到j*。由于对j*和j之间的所有j'我们知道a[j'] > a[j*]我们可以推断出a[i] + a[j'] > a[i*] + a[j*] = target，因此，所有的算法以下步骤将导致J可降低，直到它达到j*（或同等价值）没有给i机会推进并“错过”解决方案。

另一方向的解释是相似的。

Answer 2

的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)空间解决方案。

Answer 3

首先，使用radix sort对数组进行排序。那会让你回到O（kN）。然后按@PengOne建议。

Answer 4

不保证是可能的;如何选择给定的金额？

实施例：整数

2, 6, 4, 8, 12, 10 

鉴于总和的未分类的数组：

7 

??

Answer 5

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

否则 我想不到的O（n）的solution.But O（nlgn）解决方案的工作过程是这样： -

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

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

Answer 6

AS @PengOne提到它不可能在一般的东西方案中。但是，如果你对I/P数据做了一些限制。

1. 所有元素都是+或全部 - 如果不是则需要知道范围（高，低）并进行更改。
2. K，与一般元素相比，两个整数的和是稀疏的。
3. 可以销毁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是元素数btw 0到Sum in i/p A [N]

注意：如果您使用@PenOne的方法，您可以在K所以总的时间应该是N + 2K这绝对是O（N）

我们不使用任何额外的内存，但销毁I/P数组也没有坏，因为它没有任何以。

Answer 7

以下网站提供使用HashSet的是看到一个数字，然后搜索给出的总电流数 http://www.dsalgo.com/UnsortedTwoSumToK.php

Answer 8

这里HashSet的是一个解决方案女巫考虑到重复条目一个简单的解决方案。它用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

享受！

Answer 9

这里是在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 

Answer 10

下面是一个O（N）的算法。它依赖于an in-place O(N) duplicate removal algorithm，以及数组中整数的散列函数的存在。

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

其次，通过数组，并用min（x，S-x）替换每个数字x，其中S是您想要达到的总和。第三，找出数组中是否有重复项：如果'x'重复，那么'x'和'S-x'必定出现在原始数组中，并且您找到了一对。

Answer 11

Ruby实现

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 

Answer 12

我的采访过程中问同样的问题，这就是计划我的初衷。还有一项改进，允许负数，但只需要修改索引。在空间方面并不好，但我相信这里的运行时间是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”); 
} 
} 

欢迎评论家。

Answer 13

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

Answer 14

在java中，这是依赖于最大数量的阵列。 它返回一个int []，其索引为两个元素。 它是O（N）。

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

Answer 15

1. 使用计数排序到阵列为O（n）排序。

2. 取两个指针，一个从数组的第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）。

Answer 16

首先，你应该找到反向阵列=>之和减去实际阵列 然后检查这些新的数组的任何元素是否与实际阵列中的存在。用O（n×n个）的性能

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

Answer 17

朴素双环打印输出可以用O（n）的存储器，用于哈希表如下加以改进，以线性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(); 
} 

Answer 18

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中的解决方案