双指针算法-最长连续不重复子序列

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

输入：
7
1 2 3 2 4 5 6
输出：5

方法一：穷举法
对每个 i 和 j 都遍历一遍，对每个 i 和 j 都check一下中间的数据是否满足给定的条件。这样的时间复杂度是O(n^2)；数据稍微大点就会超时。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;

int arr[100];

int check(int arr[], int l, int r){
    for (int i = l+1; i <=r ; i++)
        for (int j = l; j < i; j++)
            if (arr[i] == arr[j])
                return 1;
    return 0;
}

int main(){
    int n,res=0;
     cin>>n;
    for (int i = 0; i <n; i++)cin>>arr[i];
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= i; j++)
            if (check(arr,j, i) == 0)//检查 i 和 j 之间是否有重复的数字
                res = max(res, i - j + 1);
   cout<<res;
}

方法二：双指针法
遍历数组a中的每一个元素a[i], 对于每一个i，找到j使得双指针[j, i]维护的是以a[i]结尾的最长连续不重复子序列，长度为i – j + 1, 将这一长度与r的较大者更新给r。
对于每一个i，如何确定j的位置：由于[j, i – 1]是前一步得到的最长连续不重复子序列，所以如果[j, i]中有重复元素，一定是a[i]，因此右移j直到a[i]不重复为止（由于[j, i – 1]已经是前一步的最优解，此时j只可能右移以剔除重复元素a[i]，不可能左移增加元素，因此，j具有“单调性”、本题可用双指针降低复杂度）。
用数组s记录子序列a[j ~ i]中各元素出现次数，遍历过程中对于每一个i有四步操作：
第一步：cin元素a[i] 。
第二步：将a[i]出现次数s[a[i]]加1
第三步：若a[i]重复(>1) 则右移j（s[a[j]]要减1） 确定j及更新当前长度i – j + 1给ans。
第四步：输出最大的ans。

代码实现-数组计数：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2022-07-29 07:18
 * 最后修改: 2026-05-11 12:39:39
 * 文件描述: 最长不重复数字子串，滑动窗口解法，时间复杂度 O(n)
 * 核心算法: 双指针维护无重复窗口，右指针扩张、重复时左指针收缩；
 *          本写法用数组计数，要求数字非负且值域不能过大
****************************************************************/

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 100010;
int a[N], s[N];

int main() {
   // ios::sync_with_stdio(false);
   // cin.tie(nullptr);

    int n, ans = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    for (int i = 0, j = 0; i < n; i++) {
        // 先把 a[i] 放入当前窗口，并统计它在窗口中的出现次数。
        s[a[i]]++;

        // 如果 a[i] 出现重复，就不断移动左端点 j，直到窗口重新合法。
        while (s[a[i]] > 1) {
            s[a[j]]--;
            j++;
        }

        // 此时区间 [j, i] 内所有数字都互不相同，可以更新答案。
        ans = max(ans, i - j + 1);
    }

    cout << ans;
    return 0;
}

代码实现-哈希表：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2026-05-11 12:38
 * 最后修改: 2026-05-11 12:44:06
 * 文件描述: 最长不重复数字子串，unordered_map 版滑动窗口解法，时间复杂度 O(n)
 * 核心算法: 双指针维护无重复窗口，右指针扩张、重复时左指针收缩；
 *          用无序映射(哈希表)计数，可处理负数或大值域数字
****************************************************************/

#include <algorithm>
#include <iostream>
#include <unordered_map>

using namespace std;

const int N = 100010;
int a[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, ans = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    unordered_map<int, int> cnt;
    for (int i = 0, j = 0; i < n; i++) {
        // 把 a[i] 放入窗口，并记录它在当前窗口中的出现次数。
        cnt[a[i]]++;

        // 如果 a[i] 重复，就不断收缩左端点，直到窗口恢复为无重复状态。
        while (cnt[a[i]] > 1) {
            cnt[a[j]]--;
            j++;
        }

        // 窗口合法后，用当前窗口长度更新答案。
        ans = max(ans, i - j + 1);
    }

    cout << ans;
    return 0;
}

洛谷：U224090，T650836
OJ: Y3442, Y3443

Previous Topic
Back to Lesson
Next Quiz