题解 | #最长无重复子数组# 可能是比较容易理解的2种解法

可能是比较容易理解的一种解法

import java.util.*;


public class Solution {
    /**
     * 
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        int[] dict = new int[100000];
        int maxLen = 0;
        //用于记录重复元素出现的位置的值
        int lastRepeatIndex = -1;
        //为了方便理解，这里把数组内容全部设为 -1，之后在记录的时候就可以从 0 开始，方便理解
        Arrays.fill(dict, -1);
        int i = 0;
        while(i < arr.length) {
            int value = arr[i];
            //如果当前位置的值 > lastRepeatIndex，证明当前位置已经赋过一次值了，证明元素重复
            if(dict[value] > lastRepeatIndex)
                //更新 lastRepeatIndex 为之前赋值的下标
                lastRepeatIndex = dict[value];
            //将当前下标赋值到数组相应位置
            dict[value] = i;
            //i-lastRepeatIndex = 去除重复部分
            maxLen = Math.max(maxLen, i - lastRepeatIndex);
            //arr.length-lastRepeatIndex-1 判断剩下的数有没有必要继续循环
            if(maxLen >= arr.length - lastRepeatIndex -1)
                return maxLen;
            i++;
        }
        return maxLen;
    }
    
    /* 滑动窗口，用set维护一个不重复的窗口 */
    public int maxLength_set (int[] arr) {
      int res = 0;
      Set<Integer> set = new HashSet<>();
      for(int l = 0, r = 0; r < arr.length; r++) {
          int a = arr[r];
          while(set.contains(a)) {
              set.remove(arr[l++]);
          }
          set.add(a);
          res = Math.max(res, r - l + 1);
      }
      return res;
    }
}