题解 | #最长无重复子数组#

注意到数据范围： $1 \le n \le 10^5$ ，一般而言要求时间复杂度为 $O(N)$ ，这里 $N$ 是输入数组的长度。

解题思路：

可以枚举所有的子区间，时间复杂度为 $O(N^2)$ ；
（重点）在左端点固定的情况下，如果一个子区间包含重复元素，更长的子区间也一定包含重复元素，因此更长的区间不需要枚举。

细节：

right 先向后移动，left 再向右移动；
为了检测重复的元素，需要哈希表记录出现的元素的个数。

参考代码：

import java.util.HashMap;
import java.util.Map;

public class Solution {

    public int maxLength(int[] arr) {
        int len = arr.length;
        if (len < 2) {
            return len;
        }

        // 循环不变量：arr[left..right) 没有重复元素
        int left = 0;
        int right = 0;
        Map<Integer, Integer> freq = new HashMap<>();
        int res = 1;
        while (right < len) {
            freq.put(arr[right], freq.getOrDefault(arr[right], 0) + 1);
            if (freq.get(arr[right]) == 2) {
                while (freq.get(arr[right]) == 2) {
                    freq.put(arr[left], freq.get(arr[left]) - 1);
                    left++;
                }
            }
            right++;
            res = Math.max(res, right - left);
        }
        return res;
    }
}

复杂度分析：

时间复杂度： $O(N)$ ，快指针 right 需要遍历到数组的末尾，慢指针 left 还没有遍历到数组的末尾就停了下来；
空间复杂度：取决于输入数组里出现的不同数值的个数。