题解 | #【模板】双指针#

这个题目归类为双指针，才有点名副其实~

解题思路如下：

1. 主线是右指针不断地去探索最大的符合条件的区间。
2. 在探索的过程中，如果不满足区间条件，就右移左指针，直到[i,j]区间符合条件为止。这时候计算区间长度。
3. 细节和特点：
   1. 可以用map来记录元素值出现的位置，并在右指针右移的时候用了检查新区间是否引入了重复值。不过具体代码中没用map，而是使用了数组来实现位置记录功能。
   2. 新区间的长度大于max就新开辟一个list来记录区间长度；等于max就追加区间长度；否则就舍弃该“短”区间。

具体代码：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] data = new int[n];
        for (int i = 0; i < n; i++) {
            data[i] = in.nextInt();
        }
        List<int[]> allInterval = getAllInterval(data);
        System.out.println(allInterval.size());
        for (int[] interval : allInterval) {
            System.out.printf("%d %d\n", interval[0] + 1, interval[1] + 1);
        }
    }

    public static List<int[]> getAllInterval(int[] data) {
        int n = data.length;
        // 记录value的上一次出现的index
        int[] lastValueIndex = new int[n + 1];
        Arrays.fill(lastValueIndex, -1);
        // 初始化-开始
        int max = 1;
        List<int[]> ret = new ArrayList<>();
        ret.add(new int[]{0, 0});
        int len;
        int i = 0;
        int j = 1;
        lastValueIndex[data[0]] = 0;
        // 初始化-结束
        while (j < data.length) {
            // 如果之前出现过，那就右移i，直到不再包含data[j]
            if (lastValueIndex[data[j]] != -1) {
                while (lastValueIndex[data[j]] >= 0 && i < j) {
                    lastValueIndex[data[i]] = -1;
                    i++;
                }
            }
            // 当前区间终于可以放下data[j]了
            lastValueIndex[data[j]] = j;
            len = j - i + 1;
            if (len > max) {
                // 新开list存放结果
                ret = new ArrayList<>();
                ret.add(new int[]{i, j});
                max = len;
            } else if (len == max) {
                // 同样大的区间
                ret.add(new int[]{i, j});
            }
            j++;
        }
        return ret;
    }
}