力扣数组2（C++）

一：有序数组两数之和

 注意：

• 这里要求两个索引是不同的，不能用一个索引取两次凑target,而且索引从1开始
• 存在解？唯一解？

法一：看见有序，想到二分查找

首先复习一下二分查找

int binarySearch(vector<int>& nums,int target){
    //传入数组和查找值，返回查找结果
    int L=0;
    int R=nums.size()-1;
    while(L<=R){//范围：[L,R]---左闭右闭
       int mid=(L+R)/2;
       if(nums[mid]==target) return mid;
       else if(nums[mid]>target) R=mid-1;
       else L=mid+1;
    }
    return -1;//没找到
}

本题思路：从头遍历数组，然后取后面二分查找符合题意的

class Solution {
public:
    int binarySearch(vector<int>& nums,int target,int L){
        //补充左边界
    int R=nums.size()-1;
    while(L<=R){
       int mid=(L+R)/2;
       if(nums[mid]==target) return mid;
       else if(nums[mid]>target) R=mid-1;
       else L=mid+1;
    }
    return -1;
    }
    vector<int> twoSum(vector<int>& numbers, int target) {
    int res[2]={0};
    for(int i=0;i<numbers.size();i++){
        //从i+1的位置，去找target-numbers[i]
        int p=binarySearch(numbers,target-numbers[i],i+1);
        if(p>0){
            //都加1，索引从1开始
            res[0]=i+1;
            res[1]=p+1;
        }
    }
    return vector<int>(res,res+2);//数组长是2
    }
};

法二：对撞指针 

首先将i,j指针指向有序数组两端，如果恰好相等，满足题意

如果和小了，应该扩大数值，很自然，只能将i右移

 

 如果和大了，应该缩小数值，相应的将j左移

 最后，一定在某个位置得到所求（题目保证必有解）

vector<int> twoSum(vector<int>& numbers, int target) {
      //初始化指向数组两端的指针：i和j
       int i=0;
       int j=numbers.size()-1;
       while(i<j){//题目不能让i,j对应一个元素
          if(numbers[i]+numbers[j]==target){
              int res[2]={i+1,j+1};
              return vector<int>(res,res+2);
          }
          else if(numbers[i]+numbers[j]<target) i++;
          else j--;
       }
       //假设没有解，抛出个一场
       throw invalid_argument("The input has no solution!");
    }

思路很清晰，如果没有边界，选择抛出异常也是个很好的选择

 二：最小子数组

 注意：连续子数组，如果不存在符合条件的子数组，返回 0 

---

        如图：指针i和j对应了一个区间，起始只要sum比所求小，j就不断右移，该窗口就一直扩大，直至满足了条件----和大于目标值，记录此时的窗口长度。

 

        此时，i不断右移，目的是缩小窗口，在原来和的基础上求最小。如果出现sum小于目标值，i就停止，这时候j又可以右移了。如此循环

这种双索引技术叫“滑动窗口”，利用了连续的定义，窗口值一直在变，但是i,j在数组滑动的过程，逐渐找到所求

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
    int minLen=nums.size()+1;//开始无解
          //双索引i,j形成连续子数组和的窗口:[i,j],初始化时候没窗口
          int i=0;
          int j=-1;//右小于左时没窗口
          int sum=0;
          /*串口滑动*/
          while(i<nums.size()){//i可以移动，j一定可以
              /*每次循环移动j或i----二选一，一步步移动*/
              if(j+1<nums.size()&&sum<target) //++j也要满足取值范围
                sum+=nums[++j];//先移动再求和
              else //sum>=target
                sum-=nums[i++];//先减值再移动
              /*满足条件更新minLen*/
              if(sum>=target)
                minLen=min(minLen,j-i+1);//串口大小：索引相减加一
          }
          //无解
          if(minLen==nums.size()+1) return 0;
          return minLen;
    }
};

仔细体会代码思想

三：无重复字符的最长子串 

 

 这个思路和滑动窗口一致：

既然只要求大小，那么用查找表存无重复的元素：

滑动过程-----

• 查找表不存在当前j指向元素，j不断右移扩大窗口；
• 如果找到了重复字符，那么j不断左移缩小窗口。

由于取最大，每次移动一次更新一次目标长度值

下面分别用map和set实现该算法

class Solution {
public:
    int lengthOfLongestSubstring(string s) {//用set实现
     /*初始化变量：i,j窗口指针、len返回值*/
     int i=0;
     int j=-1;//[i,j]无元素
     int len=0;//max
     set<char> record;//set查找表
     while(i<s.length()){//i可继续移动
        if(j+1<s.length()&&record.find(s[j+1])==record.end()){//找不到
            //j可以向右移动
            record.insert(s[++j]);
        }
        else{//查找表有重复元素
            record.erase(s[i++]);//i右移
        }
        //更新len
        len=max(len,j-i+1);
     }
     return len;
    }
};

class Solution {
public:
    int lengthOfLongestSubstring(string s) {//用set实现
     /*初始化变量：i,j窗口指针、len返回值*/
     int i=0;
     int j=-1;//[i,j]无元素
     int len=0;//max
     map<char,int> record;//map查找表
     while(i<s.length()){//i可继续移动
        if(j+1<s.length()&&record[s[j+1]]==0){//找不到
            //j可以向右移动
            record[s[++j]]++;
        }
        else{//查找表有重复元素
            record[s[i++]]--;//i右移
        }
        //更新len
        len=max(len,j-i+1);
     }
     return len;
    }
};