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;
}