日做力扣题1--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 * 104
• s 由英文字母、数字、符号和空格组成

解析：

1.滑动窗口：

• 使用两个指针 i 和 le 表示窗口的左右边界。

• i 是窗口的左边界，le 是窗口的右边界。

• 窗口内的字符始终是不重复的。

2.哈希集合：

• 使用 unordered_set<char> 来记录当前窗口中的字符，方便快速判断字符是否重复。

3.窗口滑动：

• 每次移动左边界 i 时，从集合中移除左边界前一个字符 s[i-1]。

• 然后移动右边界 le，直到遇到重复字符或到达字符串末尾。

• 更新当前窗口的长度 le - i + 1，并与 ret 比较，记录最大值。

代码：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 使用哈希集合记录当前窗口中的字符
        unordered_set<char> _set;
        int n = s.size();
        int ret = 0;  // 记录最长子串的长度
        int le = -1;  // 滑动窗口的右边界

        // 遍历字符串，滑动窗口的左边界是 i
        for (int i = 0; i < n; i++) {
            // 每次移动左边界时，移除左边界前一个字符
            if (i != 0) {
                _set.erase(s[i - 1]);
            }

            // 移动右边界，直到遇到重复字符
            while (le + 1 < n && !_set.count(s[le + 1])) {
                _set.insert(s[le + 1]);
                le++;
            }

            // 更新最长子串的长度
            ret = max(ret, le - i + 1);
        }

        return ret;
    }
};

时间复杂度

• 时间复杂度：O(n)，其中 n 是字符串的长度。每个字符最多被访问两次（左边界和右边界各一次）。

• 空间复杂度：O(min(m, n))，其中 m 是字符集的大小（ASCII 字符集为 128）。哈希集合最多存储 min(m, n) 个字符。