发现一对数字的阵列添加到给定的总和 [英] find pair of numbers in array that add to given sum

问题描述

问：鉴于正整数的无序排列，是有可能找到一个对整数从阵列总结为一个给定的款项？

Question: Given an unsorted array of positive integers, is it possible to find a pair of integers from that array that sum up to a given sum?

约束：这应为O（n）来完成，并就地（没有任何外部存储阵列一样，哈希地图）（你可以使用额外的变量/指针）

Constraints: This should be done in O(n) and in-place (without any external storage like arrays, hash-maps) (you can use extra variables/pointers)

如果无法做到这一点，才会有给出了同样的证明？

If this is not possible, can there be a proof given for the same?

推荐答案

如果你有一个排序的数组，你可以通过移动两个指针向中间找到这样一对为O（n​​）

If you have a sorted array you can find such a pair in O(n) by moving two pointers toward the middle

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），如果你有一个下限的数字的大小。即使是这样，一个日志n因子是非常小的，我不想刻意去把它刮了。

The sorting can be made O(N) if you have a bound on the size of the numbers (or if the the array is already sorted in the first place). Even then, a log n factor is really small and I don't want to bother to shave it off.

证明：

如果有一个解决方案（I *，J *），假设，不失一般性，即我达到 I * 在Ĵ达到Ĵ* 。由于对之间的所有 J' Ĵ* 和Ĵ我们知道 A [J']＆GT;一个[J *] 我们可以推断出 A [I] + A [J']＆GT; A [1 *] + A [J *] =目标，因此，该算法的以下所有步骤将导致J可降低，直到达到Ĵ* （或同等价值）不给我有机会向前推进和小姐的解决方案。

If there is a solution (i*, j*), suppose, without loss of generality, that i reaches i* before j reaches j*. Since for all j' between j* and j we know that a[j'] > a[j*] we can extrapolate that a[i] + a[j'] > a[i*] + a[j*] = target and, therefore, that all the following steps of the algorithm will cause j to decrease until it reaches j* (or an equal value) without giving i a chance to advance forward and "miss" the solution.

间pretation在其它方向是类似的。

The interpretation in the other direction is similar.

这篇关于发现一对数字的阵列添加到给定的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！