Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
最长无重复字符子串长度
维护两个指针pos_l和pos_r,每次pos_r右移一位,如果该字符在pos_l~pos_r-1之间已经出现过,则更新该字符最后出现的位置,同时pos_l右移一位,否则,更新最长无重复字符子串长度
一开始没想清楚pos_l的更新,WA*4


 1 #3
 2 #Runtime: 108 ms
 3 #Memory Usage: 13.5 MB
 4 
 5 class Solution(object):
 6     def lengthOfLongestSubstring(self, s):
 7         """
 8         :type s: str
 9         :rtype: int
10         """
11         dict_s = {}
12         pos_l = 0
13         pos_r = 0
14         ans = 0
15         while pos_r < len(s):
16             if s[pos_r] in dict_s:
17                 if dict_s[s[pos_r]] >= pos_l:
18                     pos_l = dict_s[s[pos_r]] + 1
19                 dict_s[s[pos_r]] = pos_r
20             else:
21                 dict_s[s[pos_r]] = pos_r
22             ans = max(ans, pos_r - pos_l + 1)
23             pos_r += 1
24         return ans

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理