【Hot100】3. 无重复字符的最长子串

中等题
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

题解：
滑动窗口
定义一个 map 数据结构存储 (k, v)，其中 key 值为字符，value 值为字符位置 +1，加 1 表示从字符位置后一个才开始不重复。

定义不重复子串的开始位置为 start，结束位置为 end

随着 end 不断遍历向后，会遇到与 [start, end] 区间内字符相同的情况，此时将字符作为 key 值，获取其 value 值，并更新 start，此时 [start, end] 区间内不存在重复字符

无论是否更新 start，都会更新其 map 数据结构和结果 ans。

map的value直接存字符的下标更好理解，在map.get(c)的地方再进行+1操作。

代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0;
        Map<Character,Integer> map = new HashMap<>();
        for(int start = 0,end = 0;end < s.length(); end++){
            char c = s.charAt(end);
            if(map.containsKey(c)){
                //相等字符第二次还没存进去，所以map中取到的就是之前存的一样字符的下标，start更新为下标的下一位置
                start = Math.max(map.get(c) + 1 ,start);
            }
            res = Math.max(end - start + 1,  res);

            map.put(c,end);

        }
        return res;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19