很简单。没什么好说的。但是在阿里实习的第四面的时候居然问到了。
大意是给出一组无序数列和目标数Z，在无序数列中找到X和Y，使得X+Y=Z。
有两种方法：
一种是排序后，同时首尾搜索。时间复杂度为O(nlgn) + O(n) = O(nlgn)。空间复杂度为O（1）
另一种是把公式转换为X = Z-Y. 从数列从头搜到尾，每个数假设为Y，因此可以得到X，找到X是否在序列中。时间复杂度为O（n），空间复杂度为O（n）
主要学习了STL的find_if、binary_search、和sort函数。更详细的可以看这篇博客
find_if函数原型为：
template <class InputIterator, class UnaryPredicate> InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred);
实现等价于：
template<class InputIterator, class UnaryPredicate> InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred) { while (first!=last) { if (pred(*first)) return first; ++first; } return last; }
第三个参数pred是个函数指针或者函数对象，它的返回值应当可转化为bool类型，参数只有一个且应当声明为const。
find_if函数的返回值为(1)如果找到了，返回指向它的迭代器，(2)否则，返回last。
binary_search函数的原型为：
template <class ForwardIterator, class T> bool binary_search (ForwardIterator first, ForwardIterator last, const T& val);
template <class ForwardIterator, class T, class Compare> bool binary_search (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
实现等价于：
template <class ForwardIterator, class T> bool binary_search (ForwardIterator first, ForwardIterator last, const T& val) { first = std::lower_bound(first,last,val); return (first!=last && !(val<*first)); }
binary_search函数的第三个参数为要查找的目标值。第四个参数为函数指针或者函数对象。它需要两个参数，返回一个bool型。
对于第一个版本，只有三个参数，使用operator < 函数来进行比较。第二个版本有四个参数，用第四个参数进行比较。
对于第一个版本，如果!(a < b) && !(b < a)那么a就与b相等。第二个版本类似，(!comp(a, b) && !comp(b, a)), 那么a与b相等。
与find_if函数区别之一是： binary_search返回的是bool型而不是迭代器。所以binary_search函数只知道是否有这个值而无法得到准确的位置
区别之二是：binary_search使用之前需要先排序。
如果迭代器不是random-access的也没关系，因为内部使用的是advance函数，只是这样复杂度就是o(n)了
sort函数原型
template <class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare> void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
第三个参数是函数指针或者函数对象。
返回值是bool型，如果为真，表示a和b的偏序关系正确，为假表示不正确，需要交换。
完整代码如下：
class Solution { struct MyStruct { int data; int original_pos; }; struct MyPred { MyPred(int d): data(d){} int data; bool operator() (MyStruct& tmp) { return tmp.data == data; } }; public: vector<int> twoSum(vector<int> &numbers, int target); static bool myCmp(const MyStruct &a, const MyStruct &b) { return a.data < b.data; } private: }; vector<int> Solution::twoSum(vector<int> &numbers, int target) { vector<MyStruct>::iterator it; vector<MyStruct>::iterator pos; vector<MyStruct> myStructVec; MyPred myPred(target); int index = 1; for (vector<int>::iterator it = numbers.begin(); it != numbers.end(); it++, ++index) { MyStruct tmp; tmp.data = *it; tmp.original_pos = index; myStructVec.push_back(tmp); } sort(myStructVec.begin(), myStructVec.end(), myCmp); for (it = myStructVec.begin(); it != myStructVec.end(); it ++) { myPred.data = target - it->data; if (myPred.data < it->data) { it = myStructVec.end(); break; } if ((pos = find_if(it + 1, myStructVec.end(), myPred)) != myStructVec.end()) break; } vector<int> ans; if (it != myStructVec.end()) { if (it->original_pos > pos->original_pos) swap(it, pos); ans.push_back(it->original_pos); ans.push_back(pos->original_pos); } return ans; }