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

给定一个长度为 n

的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

输入格式

第一行包含整数 n

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

输出格式

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

数据范围

1≤n≤10^5

输入样例：

1 2 2 3 5

输出样例：

时/空限制：1s / 64MB

解

首先明确一个概念，在计算机科学和算法题（如蓝桥杯、LeetCode）中，“连续子序列”通常指的是“连续子数组” (Continuous Subarray)，它的含义是：在原数组中位置相邻的一段元素。

它不代表数值上是连续递增的（如 1, 2, 3），也不代表数值上有某种规律。它仅仅指下标是连续的。

因此对于本题，其解题的关键在于我们要记录指针走过的数据出现了几次，一旦重复出现就记录此次最长走过的长度并重新开始记录。因此，考虑使用双指针并维护一个数组用来记录数据的出现次数。

首先接收数据

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine().trim());
        String line = bf.readLine();
        StringTokenizer st = new StringTokenizer(line);
        int []arr = new int[n];
        int maxlen = 0;
        for(int i=0;i<n;i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            if(maxlen < arr[i])maxlen = arr[i]; // 记录数据的最大值，方便开数组用来记录数据的出现次数，此处可用hash表优化
        }
        int []count = new int[maxlen+1];

然后，考虑使用两个指针left 和 right，right向前走，每走过一个元素就把当前元素出现的次数加一，也就是count[right]++;

然后一旦出现重复，即count[right] > 1;我们就记录区间长度right - left + 1并重新开始。

        int max = 0; // 最大走过的路
        int l = 0; // left
        for(int r = 0;r<n;r++) {
            int num = arr[r];
            count[num]++;
            while(count[num] > 1) {
            // 这里用循环是因为要把这段区间记录的出现的次数清零，为寻找下一段区间做准备
                int leftNum = arr[l];
                count[leftNum]--; // 清零之前的记录
                l++;
            }
            if(r - l + 1 > max) {
                max = r - l + 1;
            }
        }

        System.out.println(max);

    }
}

完整代码如下:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine().trim());
        String line = bf.readLine();
        StringTokenizer st = new StringTokenizer(line);
        int []arr = new int[n];
        int maxlen = 0;
        for(int i=0;i<n;i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            if(maxlen < arr[i])maxlen = arr[i];
        }
        int max = 0; // 最大走过的路
        int l = 0;
        int []count = new int[maxlen+1];
        for(int r = 0;r<n;r++) {
            int num = arr[r];
            count[num]++;
            while(count[num] > 1) {
                int leftNum = arr[l];
                count[leftNum]--;
                l++;
            }

            if(r - l + 1 > max) {
                max = r - l + 1;
            }
        }

        System.out.println(max);

    }
}

end

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

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

解

huohuo space

文章目录