很简单。没什么好说的。但是在阿里实习的第四面的时候居然问到了。
大意是给出一组无序数列和目标数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 = ;
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 + , 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;
}