首页 > 代码库 > Leetcode 3. Longest Substring without repeating characters

Leetcode 3. Longest Substring without repeating characters

2024-09-02 06:33:09   220人阅读

思路：类似双指针，用left标定以当前字母结尾的最长无重的substring的起点。逐个扫描字母，如果这个字母当前的substring里面没有，那么当前的substring长度就可以加一。如果这个字母已经在substring里面了，例如：

技术分享

当扫描到第二个c的时候，left应该移到d上来。并且应该将 C:2 更新为 C:6。 这里由于需要第一个c 的index，应该使用一个hash table。 如果cur后面又出现了一个a，由于目前a这个key的value小于left，所以说明current non repeating substring里面没有a。注意L14的条件。

 1 class Solution(object):
 2     def lengthOfLongestSubstring(self, s):
 3         """
 4         :type s: str
 5         :rtype: int
 6         """
 7         
 8         ans = 0
 9         left = 0
10         
11         curStr = {}
12         
13         for i in range(len(s)):
14             if s[i] in curStr and curStr[s[i]] >= left:
15                 left = curStr[s[i]] + 1
16             
17             curStr[s[i]] = i
18             
19             ans = max(ans, i-left +1)
20         
21         return ans
22

 

Leetcode 3. Longest Substring without repeating characters


联系
我们