最长无重复子数组

class Solution:
    def maxLength(self , arr: List[int]) -> int:
        # write code here
        maxValue = 0
        map = {}
        # 窗口左侧
        left = 0
        # 窗口右侧
        for right in range(len(arr)):
            if arr[right] in map.keys():
                # 记录数组在map中出现的次数
                map[arr[right]] += 1
            else:
                map[arr[right]] = 1
            # 遇到重复出现的字符，需要滑动窗口左侧，直到该字符只出现一次 
            while map[arr[right]] > 1:
                # 前面的字符可以删掉或者为0
                map[arr[left]] -= 1
                left += 1
            maxValue = max(maxValue, right - left +1)
        return maxValue

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:
    def maxLength(self , arr: List[int]) -> int:
        tmp = {}
        ret = 0
        start = -1
        for i in range(len(arr)):
            if arr[i] in tmp.keys() and tmp.get(arr[i]) > start:
                start = tmp.get(arr[i])
            tmp[arr[i]] = i
            if i - start > ret:
                ret = i - start
        return ret

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:
    def maxLength(self , arr: List[int]) -> int:
        # write code here
        n=len(arr)
        if n<=1:
            return n 
        q=[]
        res=0
        for i in range(n):
            while arr[i] in q:
            #注意这里是while,不是if,可能在q中存在多个qrr[i]
                q.pop(0)
            q.append(arr[i])
            res=max(res,len(q))
        return res

class Solution:
    def maxLength(self , arr ):
        # write code here
        n = len(arr)
        ans = []
        dic = set()
        r = 0
        for i in range(n):
            while r < n and arr[r] not in dic:
                dic.add(arr[r])
                r += 1
            if len(dic) > len(ans):
                ans = list(dic)
            if r == n-1:
                return len(ans)
            dic.remove(arr[i])
        return len(ans)

用例输入
[1,2,3,4,1,5,6,7,8,1]
预期输出
8
实际输出 5


这个测试用例没毛病吗

class Solution:
    def maxLength(self , arr: List[int]) -> int:
        # write code here
        mapping = {}  # 存放访问过的元素的索引
        i = 0  # 头指针
        j = 0  # 尾指针
        res = 0  # 记录结果
        while i < len(arr):
            # 若该元素已在字典中，且其索引在尾指针之后，表明子数组出现重复元素
            # 更新尾指针的位置为重复元素索引的后一位，同时更新重复元素的索引为头指针
            if arr[i] in mapping.keys() and mapping[arr[i]] >= j:  
                j = mapping[arr[i]] + 1
                mapping[arr[i]] = i
            # 若元素不在字典中，或者元素的索引在头指针之前，只需要添加/更新元素索引
            else:
                mapping[arr[i]] = i
            res = max(res, i-j+1)
            i += 1
        return res

哈希表 + 双指针构成滑动窗口
时间复杂度：O(n) 时间复杂度：O(n)

class Solution:
    def maxLength(self , arr: List[int]) -> int:
        mp = {}
        res = 0
        left = 0
        for right in range(len(arr)):
            if arr[right] in mp:
                mp[arr[right]] += 1
            else:
                mp[arr[right]] = 1
            while mp[arr[right]] > 1:
                mp[arr[left]] -= 1
                left += 1
            res = max(res, right - left + 1)
        return res

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

方法一：
# 个人觉得和别人思路有些不同，便将其讨论
class Solution:
    def maxLength(self , arr: List[int]) -> int:
        # write code here
        a=[]
        maxl=0
        for num in arr:
            if num in a and len(a)!=0:
                # 若num在其中将不断pop（使用a[1:]替换pop）
                while num in a:
                    a=a[1:]
            a.append(num)
            maxl=max(maxl,len(a))
        return maxl
    
方法二：

class Solution:
    def maxLength(self , arr ):
        pre_dis = 0
        maxl = 0
        dis = {}
        for i in range(len(arr)):
            num = arr[i]
            if num in dis:
                pre_dis = max(pre_dis,dis[num]) # 寻找最大左指针，意思遇到该值就会在该索引值右移动一位
            maxl = max(maxl,i+1-pre_dis) 
            dis[num]=i+1  # 保存列表值得索引，若有重复将会覆盖
        return maxl

import collections
class Solution:
    def maxLength(self , arr: List[int]) -> int:
        # write code here
        c = collections.defaultdict(int)
        l = 0 
        res = 0
        for i in range(len(arr)):
            c[arr[i]] += 1
            while len(c) != i - l + 1:
                c[arr[l]] -= 1
                if c[arr[l]] == 0:
                    c.pop(arr[l])
                l += 1
            res = max(res,i - l  + 1)
        return res