题目要求得到最长无重复子数组长度,提取关键词:“最长”、“无重复”,然而 “最长” 是建立在 “无重复” 的基础上,因此重点是 提取所有无重复的子数组,然后进行长度比较。这里的收集无重复子数组的重点是:当遇到重复数字的时候,只作废重复数字以及之前的数,而不是清空子数组,重新进行收集
例如这样的一组数据:
data = [1, 2, 3, 4, 5, 6, 7, 2, 1, 0]在第一个重复数字 2 出现之前,最长无重复子数组是:
data = [1, 2, 3, 4, 5, 6, 7]然后重复数字 2 出现,那么此时的最长子数组应该是,作废重复数字 2 以及 2 之前的数
data = [3, 4, 5, 6, 7, 2, 1, 0]然后通过这样的方式不断的提取无重复子数组,最后进行比较,代码如下:
class Solution: def maxLength(self, arr): temp = {arr[0]: 0} result = 0 for i in range(1, len(arr)): if arr[i] not in temp: temp[arr[i]] = i # 收集无重复子数组 else: # 得到大的子数组 result = max(result, len(temp)) # 得到子数组重复元素的下标 j = temp[arr[i]] # 循环获取重复元素之后的数据 temp = {arr[a]: a for a in range(j + 1, i + 1)} return max(result, len(temp))