1. 两数之和（简单）

问题：

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

通过次数1,348,299
提交次数2,732,584

思路：

①双指针扫描法（O(n)）：一个头指针一个尾指针，令头尾指针指的数相加，小了头指针后移，大了尾指针前移（即杨式矩阵的思维方式）.
***** 杨式矩阵（n*m）：行和列都是递增的.
***** 查找某值x：从右上角（本行最大，本列最小，或者左下角-本列最大，本行最小）那个数字开始，小了向下走，大了向左走，最多走n+m步，时间复杂度O(n+m).
②二分法（O(nlogn)）：前提是数据有序. 设置一个头指针p，排序后按序指向某个数x，用二分查找target-x，若找到就返回这两个数的下标，否则p后移继续查找.
③哈希表（O(n)）：unordered_map基于哈希表不保证数据有序性，map基于红黑树会保证数据有序性，哈希表无论数据有序无序都能用，维护的是当前位置之前的集合.

 1 /* 双指针扫描法 */
 2 #include <vector>
 3 using namespace std;
 4 
 5 class Solution {
 6     public:
 7         typedef pair<int, int> PII;
 8         vector<int> twoSum(vector<int>& nums, int target) {
 9             vector<PII> vec;
10             for(int i=0; i<nums.size(); i++) {
11                 vec.push_back(PII(nums[i], i));
12             }
13             sort(vec.begin(), vec.end());
14             int p=0, q=vec.size()-1;
15             while(1) {
16                 int a=vec[p].first;
17                 int b=vec[q].first;
18                 if(a+b==target) break;
19                 if(a+b<target) p++;
20                 else q--; 
21             }
22             int a=vec[p].second;
23             int b=vec[q].second;
24             if(a>b) swap(a, b);
25             vector<int> ret;
26             ret.push_back(a);
27             ret.push_back(b);
28             return ret;
29         }
30 };

 1 /* 二分法 */
 2 #include <vector>
 3 using namespace std;
 4 
 5 class Solution {
 6 public:
 7     typedef pair<int, int> PII;
 8     int my_binary_search(vector<PII> &vec, int L, int x) {
 9         int R=vec.size()-1, mid;
10         while(L<=R) {
11             mid=(L+R)>>1;
12             if(vec[mid].first==x) return vec[mid].second;
13             if(vec[mid].first<x) L=mid+1;
14             else R=mid-1;
15         }
16         return -1;
17     }
18     
19     vector<int> twoSum(vector<int>& nums, int target) {
20         vector<PII> vec;
21         vector<int> ret;
22         for(int i=0; i<nums.size(); i++) {
23             vec.push_back(PII(nums[i], i));
24         }
25         sort(vec.begin(), vec.end());
26         for(int i=0; i<vec.size(); i++) {
27             int id1=vec[i].second;
28             int id2=my_binary_search(vec, i+1, target-vec[i].first);
29             if(id2==-1) continue;
30             if(id1>id2) swap(id1, id2);
31             ret.push_back(id1);
32             ret.push_back(id2);
33             break;
34         }
35         return ret;
36     }
37 };

 1 /* 哈希表 */
 2 #include <vector>
 3 #include <unordered_map>
 4 using namespace std;
 5 
 6 class Solution {
 7 public:
 8     typedef pair<int, int> PII;
 9     vector<int> twoSum(vector<int>& nums, int target) {
10         vector<int> ret;
11         unordered_map<int, int> ha;
12         for(int i=0; i<nums.size(); i++) {
13             int val=target-nums[i];
14             if(ha.find(val)==ha.end()) {
15                 ha[nums[i]]=i;
16             }else {
17                 ret.push_back(ha[val]);
18                 ret.push_back(i);
19                 break;
20             }
21         }
22         return ret;
23     }
24 };

纪念在力扣刷的第一题——这里要感谢一下船长，虽然我不是船员.