临沂网络网站建设,沈阳外贸网站制作公司,有网站吗免费的,东莞公司网站开发Problem: AcWing 799. 最长连续不重复子序列 文章目录 思路解题方法复杂度Code 思路 这是一个求最长连续不重复子序列的问题。我们可以使用双指针#xff08;滑动窗口#xff09;的方法来解决。我们维护一个窗口#xff0c;并使用一个数组来记录窗口内元素的出现次数。当窗口… Problem: AcWing 799. 最长连续不重复子序列 文章目录 思路解题方法复杂度Code 思路 这是一个求最长连续不重复子序列的问题。我们可以使用双指针滑动窗口的方法来解决。我们维护一个窗口并使用一个数组来记录窗口内元素的出现次数。当窗口右端的元素在窗口内出现次数大于1时我们就移动窗口的左端直到窗口内所有元素都不重复。在这个过程中我们记录下窗口的最大长度这就是我们要找的最长连续不重复子序列的长度。 解题方法 我们使用两个指针i和j分别表示窗口的左端和右端。初始时i和j都指向序列的第一个元素。然后我们向右移动j增大窗口直到窗口内有重复元素。此时我们开始向右移动i缩小窗口直到窗口内没有重复元素。在这个过程中我们记录下窗口的最大长度这就是我们要找的最长连续不重复子序列的长度。 复杂度
时间复杂度: O ( n ) O(n) O(n)其中n是序列的长度。我们只需要遍历一次序列。 空间复杂度: O ( n ) O(n) O(n)我们需要一个长度为n的数组来记录窗口内元素的出现次数。 Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Main {static BufferedReader in new BufferedReader(new InputStreamReader(System.in));static PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr new StreamTokenizer(in);static int MAXN (int) (1e5 10);static int n;static int[] arr new int[MAXN];static int[] s new int[MAXN];public static void main(String[] args) throws IOException {n nextInt();for (int i 0; i n; i) {arr[i] nextInt();}int ans 0;for(int i 0, j 0; j n; j) {s[arr[j]];while(s[arr[j]] 1) {s[arr[i]]--;}ans Math.max(ans, j - i 1);}out.println(ans);out.flush();}static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}}
