package arrays;

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

/**
 * 题目:
 * 给定一个数组arr,返回arr的最长无重复子数组的长度(无重复指的是所有数字都不相同)。
 * @Author Gavin
 * @date 2022年08月06日 17:27
 */
public class array_24 {
 /**
 解题思路:
 * 用一个map来存key,需要把数组下标记录下来,需要注意的有两点,一个就是如果找到一个重复元素了那么外层下标就可以从
 * 第一个重复元素重新开始计算,这样可以大大提升性能,还有如果内层循环到末尾了就可以直接返回,因为已经是最大的了
 *
 * 与动态规划中求最长无重复字符串长度的思路一样
 */
 public static int solution(int[] arr) {
 if(arr==null) return 0;
 if(arr.length==1) return 1;
 int max = 0;
 Map<Integer,Integer> map = new HashMap<>();
 int leftIndex = 0;
 int len = arr.length;
 while(leftIndex<len){
 int repeatData = -1;
 for(int i=leftIndex;i<len;i++){
 if(map.containsKey(arr[i])){
 repeatData = arr[i];
 break;
 }
 map.put(arr[i],i);
 }
 if(repeatData==-1){
 //说明没有遇到重复数据,一直到尾巴,这时就已经产生最大值了,
 //没必要继续了
 return Math.max(max,map.size());
 }else{
 //遇到了重复数据,但还没到尾巴,最大值不确定,需要继续
 //左界限指针直接跳到重复元素(第1个)的后面
 leftIndex = map.get(repeatData)+1;
 max = Math.max(max,map.size());
 map.clear();
 }
 }

 return max;
 }
}