原题
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例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
}
(2024/3/24)
func lengthOfLongestSubstring(s string) int {
start := -1
end := -1
var maxLen int
charPos := map[byte]int{}
for {
end ++
if end == len(s){
break
}
lastPos, ok := charPos[s[end]]
if !ok || lastPos < start{
maxLen = max(maxLen, end - start)
} else{
start = lastPos
}
charPos[s[end]] = end
}
return maxLen
}
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/
