收集雪花

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 758 字

双指针加哈希表求最长无重复子段

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1464
// 题意：给 n 个时刻的雪花形状编号，求一段连续区间内形状互不相同的最大长度。
// 思路：双指针滑动窗口，哈希表记录每种形状最后出现位置，右端入窗时若该形状在窗口内则把左端推到其上次位置之后。
// 复杂度：O(n) 时间 / O(n) 空间
// 易错点：判断重复必须要求上次出现位置 >= 左端点，否则会把窗口外的历史记录误判成冲突；n 达 1e6 要关同步。
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if(!(cin>>n)) return 0;
    unordered_map<long long,int> last;
    last.reserve((size_t)n*2+1);
    last.max_load_factor(0.7);
    int ans=0,l=0;
    for(int i=0;i<n;i++){
        long long x;
        if(!(cin>>x)) return 0;
        auto it=last.find(x);
        if(it!=last.end()&&it->second>=l) l=it->second+1;
        last[x]=i;
        if(i-l+1>ans) ans=i-l+1;
    }
    cout<<ans<<'\n';
    return 0;
}

收集雪花

正文

一本通·提高篇的其它内容