问：给定一个未排序的正整数数组，是否可以从该数组中找到一对求和为给定和的整数
约束：这应该在O（n）和就地完成（没有任何外部存储，如数组、哈希映射）（您可以使用额外的变量/指针）
如果这是不可能的，有没有证据可以证明这一点
如果你有一个排序数组，你可以通过向中间移动两个指针在O（n）中找到这样一对
i=0
j=n-1
while（i<；j）{
如果（a[i]+a[j]==目标）返回（i，j）；
如果（a[i]+a[j]<；目标）i+=1；
如果（a[i]+a[j]>；目标）j-=1；
}
未找到返回；
如果您对数字的大小有一个界限（或者如果数组的第一个位置已经排序），则可以进行O（N）排序。即使这样，对数n因子还是非常小，我不想费心去刮去它
证明：
如果有一个解决方案（i*，j*），在不丧失一般性的情况下，假设i在j到达j*之前到达i*。因为对于j*和j之间的所有j'，我们知道a[j']>；a[j*]我们可以推断出a[i]+a[j']>；a[i*]+a[j*]=target，因此，算法的所有后续步骤将导致j减小，直到其达到j*（或相等值），而不会给i一个向前推进的机会，并“错过”解决方案
另一个方向的解释是类似的