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

给定一个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]

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

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))

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

题解:

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:

@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

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

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

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

关闭