leetcode 3. Longest
题目：
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
大意是找出最长无重复子串
算法思路：
这道题应该可以用动态规划做，我用的是double point的方法
一个指针start指向子串头部，另一个指针end指向子串尾部
每次递增end，判断end所指字符是否在当前子串中出现过
- 如果出现过，则将start指针向后移动一位
- 否则，将end指针向后移动，并更新最长子串长度
最后返回子串最大长度即可
该算法可以在start指针移动时进行优化，但是我优化后发现结果也没啥变化，就贴原来的代码吧
代码：
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
sLen = len(s)
if sLen == 0 or sLen == 1:
return sLen
letters = list(s)
hashSet = {}
hashSet[letters[0]] = 1
start = 0
end = 1
maxLen = 1
while end != sLen:
letter = letters[end]
if hashSet.has_key(letter) and hashSet[letter] > 0:
hashSet[letters[start]] -= 1
start += 1
continue
hashSet[letter] = 1
end += 1
if end - start > maxLen:
maxLen = end - start
return maxLen本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019/09/24 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
