从平凡一天开始刷算法 leetcode.3

难度：中等

题目：

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

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

示例 1:

输入: s = “abcabcbb”

输出: 3

解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: s = “bbbbb”

输出: 1

解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

输入: s = “pwwkew”

输出: 3

解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。

请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

思路：

2. 初始化一个空的哈希集合和两个指针，分别表示窗口的起始位置和结束位置，初始时两个指针都指向字符串的第一个字符。
3. 遍历字符串的字符，执行以下步骤：

• 判断当前字符是否在哈希集合中，如果不在，则将该字符加入哈希集合，并将结束指针向右移动一位。
• 如果当前字符在哈希集合中，表示出现重复字符，需要移动起始指针。移动起始指针的步骤如下：

• 从哈希集合中删除起始指针所指向的字符。
• 将起始指针向右移动一位。

4. 在遍历过程中，记录窗口的最大长度。
5. 返回最大长度作为结果。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Set<Character> set = new HashSet<>();
        int n = s.length();
        int maxLen = 0;
        int start = 0;
        int end = 0;
        while (start < n && end < n) {
            if (!set.contains(s.charAt(end))) {
                set.add(s.charAt(end));
                end++;
                maxLen = Math.max(maxLen, end - start);
            } else {
                set.remove(s.charAt(start));
                start++;
            }
        }
        return maxLen;
    }
}

时间复杂度：O(N)

空间复杂度：O(min(N, M))