最长连续不重复子序列

给定一个长度为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]重复则右移j(s[a[j]]要减1) -> 确定j及更新当前长度i – j + 1给r。
当a[i]重复时,先把a[j]次数减1,再右移j。

 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;
const int N = 100010;
int a[N], s[N];
int main() {
    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++) {
       s[a[i]]++;  //读入并统计数量
        while (s[a[i]] > 1) {
           s[a[j]]--;
           j++;
        }
        // while (s[a[i]] > 1) s[a[j++]]--;等同于上面三行代码
           
        ans = max(ans, i - j + 1);
    }
    cout << ans;
    return 0;
}
Scroll to Top