NC41 最长无重复子数组

描述 给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。 子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组

数据范围：0≤arr.length≤10^6，0 < arr[i]≤10^5

要求：空间复杂度 O(n)，时间复杂度 O(nlogn)

思路：将数组按照 {值：下标}的形式保存在a中。比如[2,3,4,5]保存后a={2:0,3:1,4:2,5:3}。如果有重复的数字，则会更新下标，如[2,2,3,4,3],则是{2:0}之后{2：1}，{2:1,3:2,4:3}，{2:1,3:4,4:3}。

之后对窗口进行滑动，因为下标必须是连续的，用left记录左边开始的位置，right记录右边开始的位置，left到right为窗口大小，用maxL记录最大窗口大小，maxL = right-left+1。每次循环right右移一位，并更新a。所以只需要关注left的值。当新取出的数据arr[i]不在a中时，left不需要改变。当arr[i]在a中时，若a[arr[i]]的值（重复数字的之前的下标）大于或等于left（即重复数字在窗口范围内）时，left = a[arr[i]] + 1(即将left移至重复数字的下一个数字）。每次循环都要计算窗口大小，如果当前窗口大于maxL，更新maxL

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:
    def maxLength(self , arr: List[int]) -> int:
        # write code here
        left = 0
        right = 0
        maxl = 0
        a = {}
        for i in range(len(arr)):
            right = i
            if len(a) != 0:
                if arr[i] in a:
                    if left <= a[arr[i]]:
                        left = a[arr[i]] + 1
            if (right - left) >= maxl:
                maxl = right - left + 1
            a[arr[i]] = i
        return maxl