开坑声明：最近读的一本有趣的书：《编程谜题》 打算用一个月的时间记录读书学习历程，学习解决这128道题目。

1.两数之和

【题目】

给定整数的一个数组，找出这样的两个数，它们的加和等于一个特定的目标数字(target)。

twoSum 函数应该返回两个数的索引，这两个数相加等于目标数字，其中indexl必须小于index2。请注意，返回的结果(index1和index2)不是基于0的。

可以假设对每一个输入来说，都只有一个解决方案。
输入:numbers={2,7,11,15}, target=9
输出:index1=1，index2=2

【解析】

最直观明了的解法是通过暴力搜索,使用两个嵌套的循环来遍历所有可能，时间复杂度为$O(n\ast n)$。但是很明显，这不是出题者想看到的结果。

解法一:哈希方法。

从左往右扫描一遍，然后将整数及其索引存到map中。然后再扫描一遍，对每一个整数$K$，搜索 $target-K$在map中是否存在即可。如果存在，则输出$K$及 $target-K$的下标。时间复杂度为$O(n)$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int maxn=1e6+5;
vector<int> twosum(vector<int> &numbers,int target){
   
    map<int, int> mapping;
    vector<int> result;
    for (int i = 0; i < numbers.size();i++){
   
        mapping[numbers[i]] = i;
    }
    for (int i = 0; i < numbers.size();i++){
   
        int searched = target - numbers[i];
        if(mapping.find(searched)!=mapping.end()&&i!=mapping[searched]){
   
            result.push_back(i + 1);
            result.push_back(mapping[searched] + 1);
            break;
        }
    }
    return result;
}
int main(){
   
    vector<int> numbers = {
   2, 7, 11, 15};
    int target = 9;
    vector<int> result = twosum(numbers, target);
    for (int i = 0; i < result.size();i++){
   
        cout << "index" << i << ": " << result[i] << endl;
    }
    return 0;
}

解法二:双指针扫描。

首先将数组排序，然后双指针从首尾往中间扫描。时间复杂度为$O(n\ast lgn)$。因
为要求返回原数组的下标，所以在排序的时候还要有额外的数组来存储下标信息。

双指针扫描
双指针问题是对于普通问题的一种特殊解法，往往要求问题是线性的，可以用双指针来遍历，从许多解中找到一个最大或者最小的解。双指针一般可以分别放在首尾处，用来往中间靠拢，或者者放在头部，用来划分区间。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

const int maxn=1e6+5;

struct Node{
   
    int val;
    int index;
    Node(int pVal,int pIndex):val(pVal),index(pIndex){
   }
};
static bool compare(const Node &left,const Node &right){
   
    return left.val < right.val;
}
vector<int> twosum(vector<int> &numbers,int target){
   
    vector<Node> elements;
    for (int i = 0; i < numbers.size();i++){
   
        elements.push_back(Node(numbers[i], i));
    }
    std::sort(elements.begin(), elements.end(), compare);
    int start = 0, end = numbers.size() - 1;
    vector<int> result;
    while(start<end){
   
        int sum = elements[start].val + elements[end].val;
        if(sum == target){
   
            result.push_back(elements[start].index + 1);
            if(elements[start].index<elements[end].index)
                result.push_back(elements[end].index + 1);
            else
                result.insert(result.begin(), elements[end].index + 1);
            break;
        }else if(sum>target)
            end--;
        else
            start++;
    }
    return result;
}
int main(){
   
    vector<int> numbers = {
   2, 7, 11, 15};
    int target = 9;
    vector<int> result = twosum(numbers, target);
    for (int i = 0; i < result.size();i++){
   
        cout << "index" << i << ": " << result[i] << endl;
    }
    return 0;
}