题解 | #最长无重复子数组#

最长无重复子数组

1、题意重述

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

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

换句话说，就是在数组中找出一个没有重复元素的最长子数组。

2、思路整理

使用双指针的思想：

Step1:使用两个指针left和right，其中right指向数组的第一个元素，left指向right的前一个元素。

Step2：移动right，直到[left，right]出现重复元素。

Step3：移动left，直到[left，right]不出现重复元素。

Step4：重复Step2和Step3，并保存最大值，最后返回结果。

3、代码实现

 import java.util.*;

public class Solution {
    public int maxLength (int[] arr) {
        // write code here
        if(arr.length < 2)
        {
            return arr.length;
        }
        HashMap<Integer, Integer> windows = new HashMap<>();
        int res = 0;
        int left = -1;
        //right移动
        for(int right = 0; right < arr.length; right++){
            //遇到重复数字
            if(windows.containsKey(arr[right]))
            {
                left = Math.max(left, windows.get(arr[right]));
            }
            res = Math.max(res, right-left); //保存最大值
            //将数字位置更新到windows中
            windows.put(arr[right], right);
        }
        return res; //返回结果
    }
}

4、复杂度分析

时间复杂度：一次遍历，因此时间复杂度为$O(N)O(N)$。

空间复杂度：使用HashMap，因此空间复杂度为$O(N)O(N)$，其中N为HashMap的大小。