最长连续不重复子序列(双指针)

一、算法描述

含义

  • 双指针,指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向(快慢指针)或者相反方向(对撞指针)的指针进行扫描,从而达到相应的目的。

  • 另外还可以根据序列进行区分,例如在快排中,双指针指向的是同一个序列,而归并排序中两个指针指向的是两个不同的序列。

怎么用

  • 没有必要对概念区分的很清楚,只需要知道怎么使用即可。

  • 首先想暴力解法,然后在暴力解法的基础之上,发现性质,进行优化。

  • 通过题目来理解什么是双指针吧。

二、题目描述

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

输入格式

第一行包含整数 \(n\)

第二行包含 \(n\) 个整数(均在 \(0\) ~ \(10 ^ 5\) 范围内),表示整数序列。

输出格式

共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。

数据范围

\(1 ≤ n ≤ 10 ^ 5\)

输入样例:

5
1 2 2 3 5 

输出样例:

3 

三、题目来源

AcWing算法基础课-799.最长连续不重复子序列

四、算法思路

  • 首先暴力做法就是,枚举左端点 \(l\) ,枚举右端点 \(r\) ,然后枚举区间 \([l, r]\) 判断是否有重复数字,然后更新答案,显然该做法时间复杂度会非常高,所以可以优化一下。

  • 如何优化呢?

  • 遍历数组 \(a\) 中的每一个元素 \(a[i]\) , 对于每一个\(i\),找到j使得双指针 \([j, i]\) 维护的是以 \(a[i]\) 结尾的最长连续不重复子序列,长度为 \(i - j + 1\) , 将这一长度与 \(res\) 的较大者更新给\(res\)

  • 对于每一个 \(i\) ,如何确定j的位置:由于 \([j, i - 1]\) 是前一步得到的最长连续不重复子序列,所以如果 \([j, i]\) 中有重复元素,一定是 \(a[i]\),因此右移 \(j\)直到 \(a[i]\) 不重复为止(由于 \([j, i - 1]\) 已经是前一步的最优解,此时 \(j\) 只可能右移以剔除重复元素 \(a[i]\),不可能左移增加元素,因此, \(j\) 具有“单调性”、本题可用双指针降低复杂度)。

五、源代码

#include <iostream>

using namespace std;

const int N = 100010;

int n;
int a[N], s[N];

int main()
{
    cin >> n;
    
    for (int i = 0; i < n; ++i) cin >> a[i];
    
    int res = 0;
    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;
    
    return 0;
}

热门相关:娇妻太甜:老公,要抱抱   试婚老公,要给力   这个大佬有点苟   都市捉妖人   黜龙