P1007 7unar的采样实验

一.解题思路

1.碎碎念

今天回到宿舍，闻到一股霉味

不是衣服，不是床铺

是枕头下发霉的梦想...

（如果看完对你有帮助记得点个赞再走呗嘻嘻嘻✨）

2.题目分析

给定一个数组，找到 最长的没有重复元素的连续子数组 的长度

这就是经典的 “最长无重复子串” 问题

为了能优雅的（一次遍历）实现这个算法，我们引入一个新的算法—— 滑动窗口

简单介绍一下滑动窗口：

• 使用两个指针 left 和 right 表示当前考察的窗口 [left, right]

• 用哈希表（或数组）记录窗口内每个元素最后一次出现的位置（或出现次数）

• 不断移动 right 指针扩大窗口。若发现 nums[right] 已经在窗口中存在（即出现次数≥1），则移动 left 指针直到窗口中不再包含该重复元素

• 每次窗口调整后，更新当前最长长度 max_len = max(max_len, right-left+1)

  （不清楚哈希表的去看P20004 炼气十万年 · 修为差距(哈希表解法)，在那里我对哈希表做出了讲解）

3.算法实现

1.初始化 l = 0，ans = 0，哈希表 a（记录频率）

2.遍历 r 从 0 到 n-1：

• a[num[r]]++
• 当 a[num[r]] > 1 时，循环执行 a[num[l]]-- 并 l++，直到窗口内无重复
• 更新 ans = max(ans, r-l+1)

3.输出 ans

4.复杂度

时间：O(n)

空间：O(n)

二.完整代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin>>n;
    vector<int> num(n);
    for(int i = 0;i<n;++i){
        cin>>num[i];
    }

    int ans = 0;
    unordered_map<int,int> a;
    for(int l = 0,r = 0;r<n;++r){
        a[num[r]]++;
        while(a[num[r]]>1){
            a[num[l]]--;
            l++;
        }
        ans = max(ans,r-l+1);
    }
    cout<<ans<<'\n';

    return 0;
}

PS：非专业题解！有任何错误记得联系我！！！