799. 最长连续不重复子序列 java

本文主要是介绍799. 最长连续不重复子序列 java，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

算法描述

输入格式

输出格式

数据范围

输入样例：

输出样例：

代码

算法分析

---

算法描述

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

输入格式

第一行包含整数 n�。

第二行包含 n� 个整数（均在 0∼1050∼105 范围内），表示整数序列。

输出格式

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

数据范围

1≤n≤1051≤�≤105

输入样例：

5
1 2 2 3 5

输出样例：

3

代码

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n =sc.nextInt();int[] nums = new int[n];for (int i = 0; i < n; i++) {nums[i] = sc.nextInt();}int[] counts = new int[100010];int res = 0;for(int l = 0, r = 0; l < n; l ++) {counts[nums[l]]++;while(r < n && counts[nums[l]] > 1) {counts[nums[r]]--;r++;}res = Math.max(res, l - r + 1);}System.out.println(res);}
}

算法分析

 此题属于java双指针算法，主要思想是：每当出现重复元素下标 i 时，从下标 j 开始移动，直至当 j-i 子串中不会再有重复的元素，此时可以另外使用一个数组，标记当前子串中个元素出现的次数。

 while(r < n && counts[nums[l]] > 1) {counts[nums[r]]--;r++;}

看上面这段代码，可以看到这是一个while循环，加上系统给的数据是递增的数组，所以不用担心不会出现一个新的可以使用的数组。

这篇关于799. 最长连续不重复子序列 java的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---