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

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

示例 1:

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

代码思想：

滑动窗口

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public int lengthOfLongestSubstring(String s) {

    int len = s.length();
    //最长子串
    int max = 0;

    //键为当前字符，值为当前字符的下标
    HashMap<Character, Integer> map = new HashMap<>();

    //start表示滑动窗口的开始位置，end表示滑动窗口的结束位置
    //start不动，end右移
    for (int start = 0, end = 0; end < len; end++) {

        char c = s.charAt(end);

        //如果当前字符已经存在，则需要将start移动到上一个重复字符的下一位置，同时记录最长的长度
        if (map.containsKey(c)) {
            start = Math.max(start, map.get(c) + 1);
        }
        //更新当前最大滑动窗口长度
        max = Math.max(max, end - start + 1);

        map.put(c, end);


    }
    //返回结果
    return max;


}
  • 时间复杂度：O(N)