【leetcode刷题】T58-无重复字符的最长子串
【题目】
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出:
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 。
示例 2:
输入: "bbbbb"
输出:
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 。
示例 3:
输入: "pwwkew"
输出:
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。【思路】
暴力解法：求得所有子串，判断其是否有元素重复，时间复杂度为O(n^2)。
但是，很多子串是不用判断的，比如说，s="abcacbd"，那么子串“abcac”、"abcacb"等不用判断，因为“abca”已经存在重复元素。
我们使用start表示子串开始位置，使用res存储最长无重复元素子串（只存储其长度也行）。
遍历字符串时，只要当前字符（下标为i）和子串s[start:i]有重复元素，那么start更新为子串中重复元素的后一个位置，同时判断s[start:i]长度是否大于res长度，是则更新res。比如，s="abcacbd"，当i指向第二个a时，start更新至第一个a的后一个位置，即start=1，res="abc"；同理，当i指向第二个c时，stat更新为3，res="bca"。
注意：由于最后一个元素可能不在子串中，所以，循环结束后，要判断res和s[start:]的长度大小关系。
时间复杂度为O(n)。
【代码】
python版本
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
start =
d = {}
res = ""
for i in range(len(s)):
# 元素在字典中，则s[start:i]是不重复的，和res比较并处理
# 接着删除字典中字符串从start到d[si]之间的元素
if s[i] in d:
if len(res) < i - start:
res = s[start:i]
while s[start] != s[i]:
d.pop(s[start])
start +=
start +=
d[s[i]] = i
# 最后一个元素可能不在字典中，单独处理
if len(res) < len(s) - start:
res = s[start:]
return len(res)
C++版本
class Solution {
public:
int lengthOfLongestSubstring(string s) {
map<char, int> d;
string res;
int start=;
for(int i=; i<s.size(); i++){
if(d.find(s[i]) != d.end()){
// 是否更新res
if(res.size() < i-start){
res = s.substr(start, i-start);
}
// 更新start
while(s[start] != s[i])
d.erase(s[start++]);
start++;
}
d[s[i]] = i;
}
// 最后一个元素，单独处理
if(res.size() < s.size() - start)
res = s.substr(start, s.size()-start);
return res.size();
}
};本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-05-12，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读