暴力统计 O(n^2) TLE
思路:
i:从0 ~ n-1 枚举以当前i下标为左端点的最长连续不重复子序列的长度
j:表示左端点为i时的满足条件的右端点
区间长度:j - i
import java.util.Arrays;
import java.util.Scanner;
/**
* 给定一个长度为n的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。
*/
public class Main {
int ans;
int[] hash = new int[100010];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
Main ins = new Main();
for (int i = 0; i < n; i++) nums[i] = sc.nextInt();
ins.solve(nums);
System.out.print(ins.ans);
sc.close();
}
private void solve(int[] a) {
int n = a.length;
for (int i = 0; i < n; i++) {
Arrays.fill(hash, 0);
int j = i;
for (; j < n; j++) {
if (hash[a[j]] > 0) {
break;
} else {
hash[a[j]]++;
}
}
ans = Math.max(ans, j - i);
}
}
}
双指针 O(n) AC
思路:
i:快指针 相当于区间右端点
j:慢指针,当插入下标为i的值时,出现了重复字符,j负责找到可以使其不重复的下标位置 相当于区间左端点
区间长度:i - j + 1
判断重复条件:hash[a[i]] > 0
import java.util.Arrays;
import java.util.Scanner;
/**
* 给定一个长度为n的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。
*/
public class Main {
int ans;
int[] hash = new int[100010];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
Main ins = new Main();
for (int i = 0; i < n; i++) nums[i] = sc.nextInt();
ins.solve(nums);
System.out.print(ins.ans);
sc.close();
}
private void solve(int[] a) {
int n = a.length;
for (int i = 0, j = 0; i < n; i++) {
if (hash[a[i]] > 0) {
while (hash[a[i]] > 0) {
hash[a[j]]--;
j++;
}
}
hash[a[i]]++;
ans = Math.max(ans, i - j + 1);
}
}
}