算法导论 练习 2.3-7

题目：

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

解答：

其实这是一个蛮经典的算法题目，我的leetcode题解上有这个算法，想看代码可以看看我的这篇博客

那么具体怎么实现呢？实际上这个问题有两个切入点：

1、 Θ(nlgn) ，咦？好熟悉
2、给定和 S ，那就是对某个数 C 在集合里找 S−C ，乱序不好弄啊

这两点都会引导你想到排序，有序序列就好办了：

i指向一个位置， i 将 array 分成了两部分， 0 ~ i 和 i+1 ~ n−1 ， 0 ~ i 这部分是已经处理过的部分， i+1 ~ n−1 是待处理的部分
我们将 j 指向 i+1 ； k 指向 n−1 ，然后像一次快排一样
如果 sum<target ，说明 sum 太小，此时 j++ 让 sum 变大，
如果 sum>target ，说明 sum 太大，此时 k– 让 sum 变小，
如果 sum==target ，说明已经找到元素，返回就可以