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

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) 个字符。