刷leetcodehot100返航版--双指针5/16

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}
常见问题分类：
    (1) 对于一个序列，用两个指针维护一段区间
    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

核心思想：把for i{for j}O(n^2)优化为O(n)

朴素做法——>O(n)

1.最长连续不重复子序列【看解析】

799. 最长连续不重复子序列 - AcWing题库

e.g.12245

最长连续不重复子序列：245

一般思路：确定起止点，双层for遍历，比如i是终止点，j是子序列起始点；for 0~n-1 看有没有重，计max的子序列长度

优化：在这个过程中，其实随着i增大，j是不会往左走的，因为重复的子序列不会向左增加

也就是j其实在i遍历过程是单调递增的【当然也可以不增，起码不减】，就省了j的遍历

有一点点像：

128. 最长连续序列 - 力扣（LeetCode）

主体思路是遍历子序列最后一个元素，判断j是不是要往右移

其中，判断重复与否用到的是unordered_map

#include<iostream>
#include<algorithm>//algorithm
#include<unordered_map>
using namespace std;int main(){//请找出最长的不包含重复的数的连续区间int n;cin>>n;vector<int>nums(n);for(int i = 0;i<n;i++){cin>>nums[i];}unordered_map<int,int> s;//初始化int maxNum = 0;int j = 0;//j是子序列的开头int i;for(i = 0;i<n;i++){//i是结尾s[nums[i]]++;while(i>j){// if(s[i] != s[j]){//判断不重复不合理if(s[nums[i]]>1){//每次其实新加的是第i个元素s[nums[j]]--;//删除的是j对应元素j ++;}else{//没写break;}//没保存max}maxNum = max(i-j+1,maxNum);}cout<<maxNum<<endl;
}