leetcode3. 无重复字符的最长子串 Python

概述题目链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/输入:s="pwwkew"输出:3解释:因为无重复字符的最长子串是"wke"，所以其长度为3。请注意，你的答案必须是子串的长度，"pwke"是一个子序列，不是子串。暴力解法双重循

题目链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

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

暴力解法

双重循环遍历所有区间

滑动窗口法

class Solution(object):    def lengthOfLongestSubstring(self, s):        """        :type s: str        :rtype: int        """        occ=set()        s_len=len(s)        point=-1        ans=0        for i in range(s_len):            if(i!=0):                occ.remove(s[i-1])            while point+1<s_len and s[point+1] not in occ:                occ.add(s[point+1])                point+=1            ans= max(ans,point-i+1)        return ans

复杂度分析

时间复杂度：O(N)，其中 N是字符串的长度。左指针和右指针分别会遍历整个字符串一次。

空间复杂度：O(∣Σ∣)，其中 Σ 表示字符集（即字符串中可以出现的字符），∣Σ∣ 表示字符集的大小。在本题中没有明确说明字符集，因此可以默认为所有 ASCII 码在 [0,128) 内的字符，即 ∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符，而字符最多有 ∣Σ∣ 个，因此空间复杂度为 O(∣Σ∣)。

总结

以上是内存溢出为你收集整理的leetcode3. 无重复字符的最长子串 Python全部内容，希望文章能够帮你解决leetcode3. 无重复字符的最长子串 Python所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。