题目是需要返回一个最长无重复子数组的长度,判断重复问题,有以下两种方式:
- 我们可以用当前节点的值去跟前面不重复子数组的所有元素去比较
- 使用hashmap去保存不重复子数组的键值队,也就是key=值,value=索引(index)
因为无重复子数组是会变化的,所以我们可以使用一个pre变量,保存该无重复子数组的起点,(i-pre+1)就是当前无重复子数组的长度
我们可以遍历数组,首先用hashmap获取当前元素的索引,
- 如果为空,说明当前遍历元素在无重复子数组中并不存在,可以加入无重复子数组。然后利用hashmap保存当前元素的值和索引。并计算当前无重复子数组的长度是否大于max,如果大于max则令max=当前无重复子数组的长度(i-pre+1);
- 如果不为空,说明当前遍历元素重复,重新设置无重复子数组的起点,pre=重复元素位置+1。清除hashmap中保存的pre之前的所有元素信息,让hashmap保存当前访问元素的值和索引
import java.util.*; public class Solution { /** * * @param arr int整型一维数组 the array * @return int整型 */ HashMap<Integer,Integer> map=new HashMap<>(); public int maxLength (int[] arr) { if(arr.length==0) return 0; int pre=0,now=0,max=1; for(int i=0;i<arr.length;i++){ // 更新最大长度 Integer index=map.get(arr[i]); if(index==null){ //map中不存在,即没有重复 map.put(arr[i],i); if((i-pre+1)>max) max=i-pre+1; }else{ // 重复了 int j=pre; pre=index+1; //清除map中的pre之前的所有元素 for(;j<pre;j++){ map.remove(arr[j]); } // 先清除,在添加,否则即使覆盖掉重复的也会被删除 map.put(arr[i],i); //覆盖掉之前的 } } return max; // write code here } }