题目链接：1. 两数之和

做几个小笔记吧：

1.  c++实现哈希可以使用map，查找map里是否含有某个元素时，使用find方法。时间复杂度logN。判断方法：mmp.find(……)！=mmp.end() 或者用mmp.count()!=0 (字典里的元素数量只可能是0或者1)
2. python实现哈希可以使用字典dict。查找dict里是否有某个元素时，使用get()方法。时间复杂度O1.判断方法：dict.get(……)!=None 

 class Solution {//两遍哈希 public:     vector<int> twoSum(vector<int>& nums, int target) {         map<int,int> mmp;         int length=nums.size();         for (int i=0;i<length;i++){             mmp[nums[i]]=i;         }         for(int i=0;i<length;i++){             if( mmp.find(target-nums[i])!=mmp.end() && mmp[target-nums[i]]!=i)                 return {i,mmp[target-nums[i]]};         }         return {};     } };  class Solution {//一遍哈希 public:     vector<int> twoSum(vector<int>& nums, int target) {         map<int,int>m;         int length=nums.size();         for(int i=0;i<length;i++){//检查当前遍历到元素的前一个元素是否已经记录。             if(m.find(target-nums[i])!=m.end()) return {m[target-nums[i]],i};//注意返回顺序，下标小的在前面。             m[nums[i]]=i;         }         return {};     } };  class Solution:     def twoSum(self, nums: List[int], target: int) -> List[int]:         length=len(nums)         mmp={}         for i in range(length):             mmp[nums[i]]=i;         for i in range(length):             if mmp.get(target-nums[i]) and mmp[target-nums[i]]!=i:                 return [i,mmp[target-nums[i]]]         return []

以上均不是重点。

重点：双指针法。

我理解的双指针法：

用两个指针，一前一后指向一个有序数组的头和结尾，根据题目的约束条件，头尾指针根据条件分别（只能）头向后、尾向前移动，双指针法能够达到遍历所有可能的情况。

举个例子来讲：

就这个题而言，给了我们一个数组和一个目标数字，要求找到数组中的两个数字(a1,a2)之和等于目标数字(target)。那如何利用双指针法来做呢？首先，我们要对数组排序，假设排好的顺序是从小到大。之后，我们设置两个指针：head、tail，假设它们指向的结点值分别为first、second。那么我们就应该求first+second=target。

设置head=0、tail=length-1。由于我们已经对数组排好序，所以有三种情况：

1. first+second>target（大于的情况）
2. first+second<target（小于的情况）
3. first+second==target （等于的情况）

应对以上三种情况分别有三种对策：

1. while(情况1){second-=1;}
2. while(情况2){first+=1;}
3. return ans; 

证明（最重要）：

理解了这个证明，也就明白了这种情况下的双指针法。

数组里的数字：a1,a2…………an单增（单调不降）。

1.  对于每一个head，它对应的数字first，如果和tail对应的数字second能够有：first+second==target的话，那即使在一开始first+second>target的情况下，随着tail的递减，相等的这个结果也不会被跳过。所以如果出现了小于的情况那对于当前的head肯定是不可能有等于的情况能够出现（因为tail使递减的）。
2. 所以，对于当前的tail，head如果不变，那tail取右边的值则结果为大于的情况；tail取自身以及左边的值结果则为小于的情况。
3. 所以，head只能加一。因为如果减一那肯定得到的情况是小于。
4. 出现小于的情况时，tail能不能+1而不是head+1呢？显然不能呀，因为上一轮的tail-1就是因为和的结果为大于的情况。tail再+1不就又回去了么。。。。
5. 设这时head=i、tail=j。 这样我们就已经证明了first属于[0,i]与second[j,length-1]对应的值，first+second不可能产生target。

不会用数学语言描述，证明写得一塌糊涂。

 就这个题来讲，贴一个错误的代码吧，如果题目要求是让返回数组值那不会有错，但是让返回数组下标。。。。

因为排了个序，所以数组下标乱了。就用map<int,int>保存下标。

但是map，同样的键只能保存一个值。所以，当数组中有多个值相同，且它们的和为答案的时候，就没法返回正确的下标了。

找键用的双指针法实现的。

 class Solution { public:     vector<int> twoSum(vector<int>& nums, int target) {   int length=nums.size();   int left=0,right=length-1;   //存下标   map<int,int> m;   for(int i=0;i<length;i++){    m[nums[i]]=i;   }      sort(nums.begin(),nums.end());    while(left<right){    if(nums[left]+nums[right]<target) left++;    else if(nums[left]+nums[right]>target) right--;    else {     vector<int> ans;     if(m[nums[left]]<m[nums[right]]){      ans={m[nums[left]],m[nums[right]]};//vector初始化的一种方法。     }else{      ans={m[nums[right]],m[nums[left]]};     }     return  ans;    }   }   return {};     } };