问题描述
问题:给定一个未排序的正整数数组,是否可以从该数组中找到总和为给定总和的一对整数?
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) 排序.即便如此,log 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
在之前到达i*
j
到达 j*
.因为对于 j*
和 j
之间的所有 j'
我们知道 a[j'] >a[j*]
我们可以推断 a[i] + a[j'] >a[i*] + a[j*] = target
,因此,算法的所有后续步骤将导致 j 减少,直到达到 j*
(或等于value) 而不给 i
前进的机会并错过"解决方案.
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.
另一个方向的解释类似.
The interpretation in the other direction is similar.
这篇关于在数组中查找与给定总和相加的一对数字的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!