题目描述

题目链接：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 * 10(4)
  • s 由英文字母、数字、符号和空格组成

我的题解

方法一：哈希表+滑动窗口

思路

使用左右指针记录滑动窗口的左边界和右边界，使用哈希表记录每个字符出现的位置，加速指针移动位置。

  1. 遍历字符串，如果当前字符串出现过，则更新左指针位置为最远位置
  2. 更新结果
  3. 将当前字符与位置加入哈希表
  4. 移动一位右指针

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int l = 0, r = 0, result = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        while (r < s.length()) {
            char ch = s.charAt(r);
            if (map.containsKey(ch)) {
                // 移动左指针
                l = Math.max(l, map.get(ch) + 1);
            }
            // 更新结果
            result = Math.max(result, r - l + 1);
            // 记录字符位置，移动右指针
            map.put(ch, r++);
        }
        return result;
    }
}

由题目可知，字符串由英文字母、数字、符号和空格组成，我们也可以使用数组作为哈希表，由于数组中的元素默认值为0，因此我们要记录字符的下一个位置：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int l = 0, r = 0, result = 0;
        int[] map = new int[128];
        while (r < s.length()) {
            char ch = s.charAt(r);
            // 移动左指针
            l = Math.max(l, map[ch]);
            // 更新结果
            result = Math.max(result, r - l + 1);
            // 记录字符的下一个位置，移动右指针
            map[ch] = ++r;
        }
        return result;
    }
}