发现2个号码的排序的数组等于给定的总和 [英] Find 2 numbers in an unsorted array equal to a given sum

问题描述

我们需要找到对数字在一个数组，其总和等于一个给定值。

We need to find pair of numbers in an array whose sum is equal to a given value.

A = {6,4,5,7,9,1,2}

和= 10 那么对是 - {6,4}，{9,1}

Sum = 10 Then the pairs are - {6,4} , {9,1}

我有两个方案来解决这个。

I have two solutions for this .

• 在一个O（nlogn）解决方案 - 排序+校验和与2迭代器（开始和结束）
。
• 在一个O（n）的solutiin - 散列的数组。然后检查是否总和哈希[我] 存在于哈希表或不。

• an O(nlogn) solution - sort + check sum with 2 iterators (beginning and end).
• an O(n) solutiin - hashing the array. Then checking if sum-hash[i] exists in the hashtable or not.

但是，问题是，虽然第二溶液为O（n）的时间，但使用为O（n）的空间，以及

But , the problem is that although the second solution is O(n) time , but uses O(n) space as well.

所以，我在想，如果我们能做到这一点的 O（N）时间和 O（1）的空间。这不是功课！

So , I was wondering if we could do it in O(n) time and O(1) space. And this is NOT homework!

推荐答案

使用就地基数排序和OP的有2个迭代器第一个解决方案，向对方来了。

Use in-place radix sort and OP's first solution with 2 iterators, coming towards each other.

如果阵列中的数字是没有某种多precision号码和为，例如，32位整数，则可以在2 * 32通过使用几乎没有额外的空间对它们进行排序（1每次通过位）。或者2 * 8通行证和16整数计数器（单程4位）。

If numbers in the array are not some sort of multi-precision numbers and are, for example, 32-bit integers, you can sort them in 2*32 passes using practically no additional space (1 bit per pass). Or 2*8 passes and 16 integer counters (4 bits per pass).

为2迭代器解决方案详情：

第一迭代最初指向排序后的数组的第一元素和前进向前。第二迭代最初指向数组的最后一个元素和前进后退。

First iterator initially points to first element of the sorted array and advances forward. Second iterator initially points to last element of the array and advances backward.

如果元素，通过迭代引用的总和，小于所需的值，前进第一迭代。如果它是大于所需值，前进第二迭代器。如果它等于所需的值，成功

If sum of elements, referenced by iterators, is less than the required value, advance first iterator. If it is greater than the required value, advance second iterator. If it is equal to the required value, success.

只有一个通是必要的，所以时间复杂度是O（n）。空间复杂度为O（1）。如果基数排序时，整个算法的复杂性是相同的。

Only one pass is needed, so time complexity is O(n). Space complexity is O(1). If radix sort is used, complexities of the whole algorithm are the same.

如果您有兴趣的相关问题（有超过2个数字的总和），请参见琛子集有一个固定的子集大小和的发现，一个数组，其总和接近一个给定的数字的三大要素。

If you are interested in related problems (with sum of more than 2 numbers), see "Sum-subset with a fixed subset size" and "Finding three elements in an array whose sum is closest to an given number".

这篇关于发现2个号码的排序的数组等于给定的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！