木又同学2020年第3篇解题报告
leetcode第3题:无重复字符的最长子串
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
【题目】
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
复制
【思路】
可以暴力求解,对于每一个子串,判断是否有重复字符。判断是否有重复字符,需要O(n),所以总的时间复杂度为O(n^3)
我们想想,有很多子串是没有必要判断的,比如对于"dvdf",当知道“dvd”是重复子串时,“dvdf”肯定是重复子串。因此,我们使用i表示非重复子串起始下标,j用于遍历数组,当s[j]存在于s[i:j]中,说明s[i:j+1]是重复子串,s[i:j]是以i为起点的最长非重复子串,然后更改i为s[i:j]中与s[j]相同的元素的下标。
【代码】
python版本
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
# 窗口i->j
i = 0
res = 0
for j in range(i+1, len(s)):
# 如果有重复字符,比较res和前一段非重复字符串长度,并更改i
if s[j] in s[i:j]:
res = max(res, j-i)
i += s[i:j].index(s[j]) + 1
# 不要忘了,最后要比较res和len(s)-i
res = max(res, len(s)-i)
return res
复制
C++版本
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int i = 0;
int res = 0;
for (int j=i+1; j < s.size(); j++){
// s[i:j]中是否存在s[j]
// 存在比较长度,且更新i
int offset = s.substr(i, j-i).find(s[j]);
if (offset >= 0){
res = max(res, j-i);
i += offset + 1;
}
}
// 不要忽略最后一段子串
int tmp = s.size() - i;
res = max(res, tmp);
return res;
}
};
复制