[NC]41. 最长无重复子数组

🚩传送门：牛客题目

题目

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

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

示例1

输入：[2,3,4,5] 返回值：4 说明：[2,3,4,5]是最长子数组

示例2

输入：[2,2,3,4,3] 返回值：3 说明：[2,3,4]是最长子数组

示例3

输入：[9] 返回值：1

示例4

输入：[1,2,3,1,2,3,2,2] 返回值：3 说明：最长子数组为 [1,2,3]

示例5

输入：[2,2,3,4,8,99,3] 返回值：5 说明：最长子数组为 [2,3,4,8,99]

解题思路：双指针

利用 存储数据来进行判重，当遇到重复的冲突数据的时候 。需要判断 左边冲突点 和 pre 谁数字更大。

谁的下标更大，谁就是最新的 pre

pre：用来存储合法区间 (start，end]中的 。

的意义为了计算从 到 的有效区间

算法流程：

1. 遇到一个数字首先判重，是否和中的数字产生冲突

   冲突：在 pre 和左边冲突点中选择较大值赋值给

2. 利用公式 计算有效区间长度，看能否刷新 最大长度值

3. 将当前的数字和下标加入用于判重

   无论是否包含此数都刷新重新存储

复杂度分析

时间复杂度： ，其中 是数组的长度。

空间复杂度： ，其中 k 去重个数

我的代码

public class Solution {
    public static int maxLength(int[] arr) {
        HashMap< Integer, Integer > map = new HashMap < > ();
        int res=0;
        int pre=-1;    //pre指向合法区间(start,end]的start
        for(int i=0;i<arr.length;i++){
            //1.判断是否产生冲突点
            if(map.containsKey(arr[i]))
                pre=Math.max(map.get(arr[i]),pre);     //pre应选此次和上一次的冲突点的较大值    
            //2.更新res:更新公式 i-pre
            res=Math.max(res,i-pre);
            //3.将当前最新元素入map用于判断重复
            map.put(arr[i], i);
        }
        return res;
    }
}