重新学习一遍<算法导论>，看到了这个问题：

描述一个运行时间为O(nlgn)的算法，使之能在给定一个由n个整数构成的集合S和另一个整数 X 时，判断出S中是否存在有两个其和刚好等于 X 的元素。

Solution：

（1）->对整个集合进行排序，可以用快排（含有小文件策略、三者取中策略），时间复杂度O(nlogn)，形成一个数组A[n]。

 ->设定两个下标pBegin和pEnd，分别指向数组A[n]的头尾，pBegin = 0，pEnd = n -1。

 ->若（A[pBegin] +A[pEnd]）== X，找到元素对；

 ->若（A[pBegin] +A[pEnd]）> X，则表示所需的元素对应该要小一些，对于已经排好序的非降序数组，只需要将--pEnd即可；

 ->若（A[pBegin] +A[pEnd]）< X，则表示所需的元素对应该要大一些，只需要将++pBegin即可；

 ->直到 pBegin  == pEnd 。总共的时间复杂度为O(nlogn+n)，空间复杂度O(1)。

证明的思路：利用反证法，假如 （A[m] + A[k] ）== X。初始化时，pBegin <= m，pEnd >= k。

首先证明在移动过程中pBegin 不可能大于m，假如pBegin 大于m，则在ipBegin 大于m之前，必有pBegin 必会有一次等于m，当pBegin 等于m时，pEnd 是大于k的，这时的A[pBegin] + A[pEnd] > X，所以pBegin 会一直停留在m处，直到pEnd 移动到k为止，所以pBegin 不会移动超过m。

同理可以证明pEnd 不会小于k，算法是正确。

（2）->对于较小的X，可以考虑利用Hash的思路，直接声明一个大小为X的数组S[X]，初始化全部元素为0。消耗X个辅助空间。

 ->遍历一次集合，对于所有小于等于X的元素k，令S[k]++，时间复杂度n；

 ->遍历数组S[X]，对于不为0的元素下标m（S[m]!=0），查看S[X-m]是否为0；若m == X-m，查看S[m]>=2是否为真。

 ->总共的时间复杂度为O(X+n)，空间复杂度O(X)。但是是在X较小的情况下。

 ->同时这个方法可以找出所有的元素对！

拓展问题：

（1）是否存在三个元素之和正好等于给定值X？ 

【假如 A[m]+A[k]+A[s] == X，对于所有元素i，是否在集合S(除去i)中有两个元素之和等于 X-A[i]，n个元素对应n个上述的两个元素和的子问题。时间复杂度应该是O(nlogn+n^2)】不知是否有更好的思路？

（2）给定n个整数的集合S，输出集合S中所有满足 a+b=c 的整数a、b、c。

【类似1的解法，其实就是 a+b-c=0的变形】