如果您有一个已排序的数组，则可以通过将两个指针移到中间来在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机会前进并“错过”解。
在另一个方向上的解释是相似的。
