#
# 
# @param arr int整型一维数组 the array
# @return int整型

# 对于这一道题最先想到的方法就是枚举，我们可以尝试把数组中每一个元素都当作开头，一个一个去试
# 假设有数组[1, 2, 5, 2 ,3]

# 思路：那么它的最长无重复子数组要么就是以1开头，要么就是以第一个2开头，要么就是以5开头
#       要么就是以第二个2开头，要么就是以3开头
# 所以： 我们去看以1开头的时候这个数组能有多长，以此类推
# 最后： 选出最长的，就是答案

# 最开始我用两层for循环实现，但是超时,时间复杂度为：O(N平方)
# 最后用双指针实现，时间复杂度为O(N)

# 实现步骤：
#     循环结束的条件：右指针走出了整个数组(right == len(arr) ) 
#     1、左右指针都指向第一个元素
#     2、判断arr[right]是否已经出现过了，如果没出现，就加到字典中去，判断一下是否要更新最大长度，
#        右指针向右移动一位
#     3、如果出现了，就把arr[left]从字典中移除，将左指针右移一位，
#        此时arr[left]到arr[right]一定没有重复元素(重复步骤2)

#  ### 重点：第三步中的左指针右移就相当于重新选择一个元素当作子数组的开头
#  ###      只是我们没必要从以这个元素的开头长度为1的子数组开始枚举了
#  ###      因为我们知道从arr[left]到arr[right]没有重复元素
#  ###      所以默认以这个元素开头的满足条件的子数组的初始长度为right-left+1

class Solution:
    def maxLength(self , arr ):
        # write code here
        maxLen = -1
        left = 0
        right = 0
        lenght = len(arr)
        dic = {}
        while right < lenght:
            if arr[right] not in dic:
                dic[arr[right]] = right
                maxLen = max(maxLen, right - left + 1)
                right += 1
            else:
                dic.pop(arr[left])
                left += 1
        return maxLen