【每日算法】无重复字符的最长子串

目录

题目描述

这是 LeetCode 上的 3. 无重复字符的最长子串

难度为 【中等】

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

示例 4:

输入: s = ""
输出: 0

提示:

0 <= s.length <= 5 * 10^4
s 由英文字母、数字、符号和空格组成

题目要求及思路

最长子串要求是连续的字符串,切不重复,可以使用set来保存已经访问过的字符,如果重复就删除set中之前保存的字符。
使用set模拟滑动窗口,先右移扩大窗口,使窗口内的元素不重复,当发现字符已经重复时,再移动左侧的边界,使期缩小,直到窗口内没有重复的元素为止,然后计算此时的子串长度,一直重复上面的步骤,直到字符串尾部
【每日算法】无重复字符的最长子串

代码实现

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        #使用可变的滑动窗口,移动右边界扩大窗口,移动左边界缩小窗口
        # s = "abcabcbb"
        i=0
        exists=set()
        res=0#返回的结果
        for j,v in enumerate(s):
            while v in exists:#如果已经存在
                exists.remove(s[i])#移除之前的一个元素
                i+=1
            res=max(res,j-i+1)
            exists.add(v)#加入新的元素
        # print(exists)
        return res
上一篇:ln: failed to create symbolic link ‘/usr/bin/python’: File exists


下一篇:File类判断功能的方法