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

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

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

• 示例 1：

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

• 示例 2：

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

• 示例 3：

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

• 提示：

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

思路

使用滑动窗口和双指针的方法，通过移动 right 指针来扩展窗口，移动 left 指针来缩小窗口。

代码说明

1. 初始化：

   • 如果字符串为空，直接返回 0。
   • 使用一个 set 存储滑动窗口内的字符，确保没有重复字符。
   • 初始化两个指针 left 和 right，都指向字符串的开头。

2. 滑动窗口：

   • 移动 right 指针遍历字符串。
   • 如果当前字符不在集合中，表示没有重复字符，移动 right 指针，将该字符加入集合，更新 maxLength。
   • 如果当前字符在集合中，表示有重复字符，移动 left 指针，直到滑动窗口中没有重复字符为止。

3. 返回结果：

   • 最终，返回 maxLength 作为结果。

• 时间复杂度:O(n)
• 空间复杂度:O(n)

代码

public int lengthOfLongestSubstring(String s) {
    // 如果字符串为空，直接返回 0
    if (s.isEmpty()) {
        return 0;
    }
    // 哈希集合，记录每个字符是否出现过
    HashSet<Character> set = new HashSet<>();
    int maxLen = 1;
    // 使用两个指针维护一个滑动窗口，初始都指向字符串开头
    int left = 0;
    int right = 0;
    // 移动右指针遍历字符串
    for (int i = 0; i < s.length(); i++) {
        while (right < s.length()) {
            // 如果当前字符不在集合中，表示没有重复字符，移动右指针
            if (!set.contains(s.charAt(right))) {
                set.add(s.charAt(right));
                right++;
                // 更新最长子串的长度
                maxLen = Math.max(maxLen, right - left);
            } else {
                // 如果当前字符在集合中，表示有重复字符，移动左指针
                set.remove(s.charAt(left));
                left++;
            }
        }
    }
    return maxLen;
}