【每日一题0702】 返回 list 最长无重复元素子list的长度

兴趣爱好交流 每日一题
1

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

示例1

输入：
[2,3,4,5]
返回值：
[2,3,4,5]是最长子list

示例2

输入：
[2,2,3,4,3]
返回值：
3
说明：
[2,3,4]是最长子list

示例3

输入：
[9]
返回值：
1

示例4

输入：
[1,2,3,1,2,3,2,2]
返回值：
3
说明：
最长子list为[1,2,3]

示例5

输入：
[2,2,3,4,8,99,3]
返回值：
5
说明：
最长子list为[2,3,4,8,99]

题目来源：最长无重复子数组_牛客题霸_牛客网

2 
lsit = [2,2,3,4,8,99,3]
def ruturnList(list):
    listx = []
    for x in list:
        if x not in listx:
            listx.append(x)
    listx.sort()
    return listx, len(listx)
print(ruturnList(lsit))
4

去重了之后排了个序，这样不ok吧

5

题解：

def longest_no_dup(nums:list):
 
    count = []
    sub = []
    cursor = 0
    for i, item in enumerate(nums):
        # 如果存在重复，将子串剔除重复元素前的所有全素，重置指针位置
        if item in sub:
            cursor += sub.index(item) + 1
            sub = nums[cursor:i]
        # 更新子串，记录长度 
        sub.append(item)
        count.append(i - cursor + 1)
        
    return max(count)

assert 4 == longest_no_dup([2,3,4,5])
assert 3 == longest_no_dup([2,2,3,4,3])
assert 1 == longest_no_dup([9])
assert 3 == longest_no_dup([1,2,3,1,2,3,2,2])
assert 5 == longest_no_dup([2,2,3,4,8,99,3])

:partying_face: :partying_face: :partying_face: :partying_face: :partying_face: :partying_face:

6

@yxtong1234_0937 想法很好！但是实际肯能不能满足题目要求。因为原列表是无序的。去重也将导致你无法判断子串的开始和结束位置。

例如，[1,2,5,1,2]，它的不重复子串将有：[1]，[1,2]，[1,2,5]，[2,5,1]，[5,1,2]，根据题目要求应返回最大长度是3。去重排序你会意外得[5]，将其作为长度是不合理的。

继续开动聪明的小脑袋思考思考吧～

@zhanfengzh_9391 很棒！这个解题方法还有一个小bug，例如考虑一个特殊场景：[1,2,3,2,5,2,7,2,9]，预期最长子串应该是[1,2,3]，最大连续不重复子串的长度预期应该是3，实际你的函数输出长度将是6。

7

直接获取sub的长度为什么不行，反正要多一步count.append(i - cursor + 1) 这点不是很理解 麻烦小佛老师讲讲 @Amoyshmily

8

我理解的是sub只是每次用来存储子串的，最后获取sub的长度，得到的是从最后一个元素往前数最长不重复子串的长度，不一定是最大的

9

@sunyanfen 放心，都可以的。count.append(i - cursor + 1) 可以用 count.append(len(sub))是一样效果。用减法主要是基于性能考虑的。纯数字计算的速度我认为可能会高于len()函数，所以就这样写了。另外，这个不是标准答案哈，只是参考思路，哈～ :partying_face: