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

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因子确实很小，我也不想打扰。

证明：

如果有一个解决方案(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机会前进并“错过”解。

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