$$\color{Red}{最长连续不重复子序列-【双指针】(三种语言)}$$
这里附带打个广告——————我做的所有的题解
包括基础提高以及一些零散刷的各种各样的题
题目介绍
给定一个长度为 n 的整数数列,请你计算数列中的逆序对的数量。
逆序对的定义如下:对于数列的第 i 个和第 j 个元素,如果满足 i < j 且 a[i] > a[j],则其为一个逆序对;否则不是。
输入格式
第一行包含整数 n,表示数列的长度。
第二行包含 n 个整数,表示整个数列。
输出格式
输出一个整数,表示逆序对的个数。
数据范围
1 ≤ n ≤ 100000
数列中的元素的取值范围 [1, 10 ^ 9]
输入样例:
6
2 3 4 5 6 1
输出样例:
5
java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int n, N = 100010;
static int[] cnt = new int[N];
static int[] a = new int[N];
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
n = Integer.parseInt(br.readLine());
String [] s = br.readLine().split(" ");
int res = 0;
for (int i = 0, j = 0; j < n; j++) {
a[j] = Integer.parseInt(s[j]);
cnt[a[j]] += 1;
while(cnt[a[j]] > 1) cnt[a[i++]] -= 1;
res = Math.max(res, j - i + 1);
}
System.out.println(res);
}
}
python3
n = int(input())
arr = [int(x) for x in input().split()]
j, ans = 0, 0
d = {}
for i in range(n):
if d.get(arr[i],False):
d[arr[i]] += 1
while d[arr[i]] > 1 and j <= i:
d[arr[j]] -= 1
j += 1
else:
d[arr[i]] = 1
ans = max(ans, i - j + 1)
print(ans)
C++
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int main()
{
int n;
scanf("%d", &n);
int res = 0;
for(int i=0, j=0; i<n; i++)
{
cin >> a[i];
b[a[i]] ++;
while(b[a[i]] > 1) b[a[j++]] --;
//每更新一个a[i]都会计数!!这是精髓
res = max(res, i - j + 1);
}
cout << res;
return 0;
}