原题
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
解法
思想
滑动窗口,将出现的字符和下标在哈希表中对应起来。
该问题的关键是获取所有不重复字符子串的长度,比较出最大的长度,我们用last记录当前计算的子串的第一个字符位置。
那么不重复字符子串的长度的计算方法就是:
假设从last开始都是不重复字符,如果遇到一个在哈希集中出现过的字符并且是last或last之后的,说明遇到了重复字符,如下图的d,则此时的不重复字符子串adv
的长度为第二个d之前的长度3-0=3
。然后将last移到v上(第一个d后面的那个元素,这样新子串中就不会有两个d了),便可继续进行操作。
这样依次进行无重复字符子串的长度计算,当最后遍历到最后一个字符c的时候,都和last以及last之后出现的字符无重复,那么此时最后计算的子串vdfc
的长度是5-2+1=4
(因为c是计入子串的)

那么假设最后一个字符是v,当最后遍历到最后一个字符v的时候,和当前子串中的v重复了(vdfv
),那么和之前计算子串长度的方法一样是5-2=3
(最后一个v不计入长度)

代码
Java
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character,Integer> map = new HashMap<>();
int max = 0;
int last = 0;
char[] chars = s.toCharArray();
for(int i = 0;i<chars.length;i++){
if(map.containsKey(chars[i])&&map.get(chars[i])>=last){
if(i-last>=max) max = i-last;
last = map.get(chars[i]) + 1;
}else if(i == chars.length-1&&i-last+1>=max){
max = i-last+1;
}
map.put(chars[i],i);
}
return max;
}
}
Go(2020/07/05)
func lengthOfLongestSubstring(s string) int {
start := 0
max := 0
m := map[byte]int{}
for i,c := range []byte(s){
if v,ok := m[c]; ok && v >= start{
if i-v > max { max = i-v }
start = v + 1
}else{
if i-start+1 > max {max = i-start+1}
}
m[c] = i
}
return max
}
go需要注意,如果需要兼容中文字符串,需要怎么处理:
func lengthOfLongestSubstring(s string) int {
start := 0
max := 0
m := map[rune]int{}
for i,c := range []rune(s){
if v,ok := m[c]; ok && v >= start{
if i-v > max { max = i-v }
start = v + 1
}else{
if i-start+1 > max {max = i-start+1}
}
m[c] = i
}
return max
}
Python
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
m = {}
start = 0
maxLen = 0
for i,c in enumerate(s):
v = m.get(c)
if v != None and v >= start:
maxLen = max(i-v,maxLen)
start = v+1
else:
maxLen = max(i-start+1,maxLen)
m[c] = i
return maxLen
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode3-%e6%97%a0%e9%87%8d%e5%a4%8d%e5%ad%97%e7%ac%a6%e7%9a%84%e6%9c%80%e9%95%bf%e5%ad%90%e4%b8%b2/