在数组中找到加到给定总和的数字对

在数组中找到加到给定总和的数字对

如果您有一个已排序的数组，则可以通过将两个指针移到中间来在O（n）中找到这样的一对

i = 0j = n-1while(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

我们都知道

a[j'] >a[j*]

我们可以外推

a[i] + a[j'] > a[i*] + a[j*] =target

，因此，该算法的所有后续步骤将导致j减小直至达到

j*

（或相等值），而没有

i

机会前进并“错过”解。

在另一个方向上的解释是相似的。