算法-编程之美2.12快速寻找满足条件的两个数:解法三: 求证明

Question

题目: 能否快速找出一个数组的两个数字，让这两个数字之和等于一个给定的值sum，假设数组至少一组符合要求的解。
解法三: 先对数组排序，然后再数组的开始和结尾处维护两个游标i，j，然后我们比较arr[i]+arr[j]与sum的大小，如果arr[i]+arr[j]>sum，则i++，如果<sum，则j--，直到找到arr[i]+arr[j]=sum，这样，复杂度即为遍历O(N)，排序O(NlogN)。

感觉很好很强大, 但本人愚钝, 只能大概理解是对O(n^2)的解空间每次做跳跃判断. 请给出算法可行性证明.

Answer 1

这个解法的主要疑问是只做O（N）的遍历会不会漏解。证明如下：

遍历时只有一个判断条件：比较arr[i]+arr[j]与sum的大小。
设sum = a + b (a<b), arr[i]<arr[j] (数组从小到大排序，这点和题目中描述的相反，我习惯从小到大，见谅)
注意到，arr[1] <= a, arr[n] >= b;
1.若相等，就出结果了；
2.若arr[i]+arr[j] < sum,则i++，直到arr[i]+arr[j] > sum。则arr[i-1]+arr[j] < sum,而arr[j] >= b,则arr[i-1] < a,于是arr[i] <= a,所以arr[i] <= a,arr[j] >= b依然成立。
3.同2可证，arr[i] <= a, arr[j] >=b依然成立。
现在可得一个结论arr[i] <= a, arr[j] >=b总是成立，而若arr[i]+arr[j] != sum，上述循环不会停止，直到arr[i]+arr[j] == sum.

Answer 2

1.解答这个题目的核心是要先对数组排序，要求快速，就要排序。。不排序的方法用时都没有排序方法用时短。
2.排序后，第二个必须是有两个游标，位于数组首尾。何种排序不影响。以从小到大为例：首尾相加若小于这个数，由于尾数是这个数组的最大数，因此表示另一个加数下了，应该换个大一点的加数，所以小于这个数时是数组首的游标后移；若是首尾数之和大于这个数，参照第一种情况的思想，应该会清楚的得到答案。
3.按照2中的思想，直至找到相等的情况，就找到了这两个数了。

Answer 3

其实这个题目画个图的反而好理解点
设数组的元素为 a1, a2, ... an ，且 a1 < a2 < ... < an
设sum = a + b （a < b）
设数组的元素为某一个线段上的所有点，则a和b分布的情况如果图 1 - 4 所示

以a1为左端点，an为右端点进行位移，必然左端点会和a点相遇，右端点会和b点相遇。

以图5来说，设绿色区间为x，橙色区间为y
则有关系 x > y 和 x <= y，当 x > y 时，进行左端点位移，反之则右端点位移

x = a - a1, y = an - b

x > y 则 a - a1 > an - b => a + b > a1 + an => sum > a1 + an

所以当 sum > a1 + an， 进行i++， 反之j--， 则一定会有 a[i] = a, a[j] = b