[Leetcode][python]Longest Substring Without Repeating Characters/无重复字符的最长子串

墨蓝 2022-06-10 02:11 75阅读 0赞

## 题目大意 ##

给定一个字符串，从中找出不含重复字符的最长子串的长度。  
例如，”abcabcbb”的不含重复字母的最长子串为”abc”，其长度是3。”bbbbb”的最长子串是”b”，长度为1。

## 解题思路 ##

**哈希表**\+**双指针**

来自[博客][Link 1]

变量start和end分别记录子串的起点和终点，从左向右逐字符遍历原始字符串，每次将end + 1，字典countDict存储当前子串中各字符的个数  
当新增字符c的计数 > 1时，表明已经有重复，**向右移动起点start，并将s\[start\]在字典中的计数 - 1，直到countDict\[c\]不大于1为止更新最大长度**

## 代码 ##

class Solution(object):
        def lengthOfLongestSubstring(self, s):
            """
            :type s: str
            :rtype: int
            """
            ans, start, end = 0, 0, 0
            countDict = {}
            for c in s:
                end += 1
                countDict[c] = countDict.get(c, 0) + 1  # countDict.get(c, 0)意思是：若c不存在直接返回0
                while countDict[c] > 1:
                    countDict[s[start]] -= 1
                    start += 1
                ans = max(ans, end - start)
            return ans

优化思路：遇到重复的字母，直接跳到重复字母的后面一个，而不是像之前那样慢慢向右移动！

class Solution(object):
        def lengthOfLongestSubstring(self, s):
            """
            :type s: str
            :rtype: int
            """
            used = {}
            max_length = start = 0
            for i, c in enumerate(s):
                if c in used and start <= used[c]:
                    start = used[c] + 1
                else:
                    max_length = max(max_length, i - start + 1)
    
                used[c] = i
    
            return max_length

## 总结 ##

*  countDict.get(c, 0)

[Link 1]: http://bookshadow.com/weblog/2015/04/05/leetcode-longest-substring-without-repeating-characters/