描述

给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。

子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组

类似题目：最长不含重复字符的子字符串

思路1：滑动窗口

  1. 使用left、right双指针表示滑动窗口
  2. 每次窗口扩大时，遍历窗口中的元素
  3. 如果窗口中包含新元素，则缩小左边界
public class Solution {
    public int maxLength (int[] arr) {
        int ret = 0;
        int left = 0;
        int right = 0;
        while(right < arr.length) {
            for(int i = left; i < right; i++) {
                if(arr[i] == arr[right]) {
                    left = i + 1;
                    break;
                }
            }
            right++;
            ret = Math.max(ret, right - left);
        }
        return ret;
    }
}

思路2：滑动窗口+Map

同思路1，只不过使用Map记录滑动窗口中元素的最大位置，通过Hash查找，不需要遍历

  1. 使用left、right双指针表示滑动窗口
  2. 使用Map记录每个元素的最大索引
  3. 出现重复元素时，找到重复元素的索引，缩小滑动窗口
public class Solution {
    public int maxLength (int[] arr) {
        int ret = 0;
        Map<Integer, Integer> map = new HashMap<>();
        int left = 0;
        int right = 0;
        while(right < arr.length) {
            if(map.containsKey(arr[right])) {
                //重复元素可能在滑动窗口之外，此时左边界不需要移动
                left = Math.max(left, map.get(arr[right]) + 1);
            }
            map.put(arr[right], right);
            right++;
            ret = Math.max(ret, right - left);
        }
        return ret;
    }
}

思路3：滑动窗口+队列

类似思路1，使用队列存储滑动窗口中的元素，需要开辟额外的空间

  1. 使用left、right双指针表示滑动窗口
  2. 使用队列存储滑动窗口内的元素
  3. 出现重复元素时，缩小滑动窗口，将左边的元素全部移出
public class Solution {
    public int maxLength (int[] arr) {
        int ret = 0;
        Queue<Integer> queue = new LinkedList<>();
        for(int num : arr) {
            while(queue.contains(num)) {
                queue.poll();
            }
            queue.offer(num);
            ret = Math.max(ret, queue.size());
        }
        return ret;
    }
}