博客

给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

本题使用双指针算法，双指针算法主要用于优化暴力遍历数组的题目，从而获得更好的时间复杂度。考虑使用双指针算法前先思考题目的暴力解法。如本题暴力解法可以是直接两个指针遍历数组，找出最长的不包含重复的数的连续区间，时间复杂度为O(n

²

)。



本题我们要用双指针维护一个满足不包含重复数字的区间，i指针在数组前面进行遍历，i指针每到一个位置需要找出距离i指针最远的，小于i指针位置且满足区间无重复元素的j指针，长度i – j + 1则为该区间长度。基于这个思想，i、j指针只需要正序的遍历数组一次，不考虑判断区间是否满足条件的情况下时间复杂度为O(2n)。

那么怎么用较少的时间耗费，完成多次判断区间是否有重复元素的任务呢？

可以用空间换时间的方法，设定一个足够大的数组，记录元素出现的次数，动态的进行维护，很显然只有区间内元素出现次数等于1才满足条件。当i指针在前面移动导致区间元素出现次数大于1时，就必须通过移动j指针，直到区间元素出现次数满足条件，此时的区间满足条件。

代码如下所示：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, a[N], s[N];
int main()
{
    int res = 0;
    cin >> n;
    for(int i = 0; i < n; i++)cin >> a[i];
    for(int i = 0, j = 0; i < n; i++)
    {
        s[a[i]]++;
        while(j < i && s[a[i]] > 1)
        {
            s[a[j]]--;
            j++;
        }
        res = max(res, i - j + 1);
    }
    cout << res << endl;
}