数据结构-线性表(数组)-双指针-＞数组逼近(左右指针)167&15*

1. 两数之和 II - 输入有序数组

• 思路
  我的思路：从数组两端逼近target，左右指针指向元素和大于target，则右指针左移；反之，左值针右移。
  其他：确定一个元素，找target-nums[i]，有序数组，二分查找。
• 代码
  我的做法：

class Solution {
public:
    vector twoSum(vector& numbers, int target) {
        int len = numbers.size();
        int left = 0,right = len-1;
        while(left < right){
            if(numbers[left]+numbers[right] > target) --right;
            else if(numbers[left]+numbers[right] < target) ++left;
            else break;
        }
        return {left+1,right+1};
    }
};

二分查找：

class Solution {
public:
    vector twoSum(vector& numbers, int target) {
        int len = numbers.size();
        int temp = 0,j = 0,i = 0;
        for(i;i
            temp = target - numbers[i];
            int left = i+1,right = len-1;
            while(left<=right){
                int mid = left + (right-left)/2;
                if(numbers[mid]>temp) right = mid - 1;
                else if(numbers[mid]j = mid;return {i+1,j+1};}
            }
            if(j != 0) break;
        }
        return {i+1,j+1};
    }
};

• 总结学习
  hash表可用来对无序数组进行查找，有序数组要想到二分法和双指针。

三数之和

• 思路
  为什么进行排序：避免计算重复
  我没做出来的原因：题目要求不重复，我没有想到对数组排序后可能相邻元素有重复的。
  重点：对相邻元素去重 continue关键字
• 代码

vector> threeSum(vector& nums) {
        int len = nums.size();
        sort(nums.begin(),nums.end());
        vector> res;
        int left = 0,right = 0;
        int i = 0;
        for(i; i
            if(i>0 && nums[i] == nums[i-1]) continue;//去重
            left = i + 1;
            right = len - 1;
            while(left
                if(nums[left]+nums[right]>(-nums[i])) --right;
                else if(nums[left]+nums[right]<-nums[i]) ++left;
                else {
                    res.push_back({nums[i],nums[left],nums[right]});
                    ++left;
                    --right;
                    while(left 
总结
 双指针方法对，但是要会再加点别的，比如本题的去重。