【算法面试必刷】

目录

题目

​编辑

题目链接

思路

复杂度

时间复杂度：O(n)

空间复杂度：O(min(n, m))

代码

题目

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

示例 1:

输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。
示例 2:

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

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

题目链接

3. 无重复字符的最长子串 – 力扣（LeetCode）https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-100-liked

思路

核心思想：滑动窗口 + 哈希集合

滑动窗口：

• 窗口定义：当前考察的无重复字符的子串

• 左指针（left）：窗口的左边界

• 右指针（right）：窗口的右边界，不断向右扩展

哈希集合的作用：

复杂度

时间复杂度：O(n)

虽然代码中有嵌套循环（while 在 for 内部），但每个字符最多被访问两次：

分析：

外层循环：右指针 right 移动 n 次
内层 while 循环：左指针 left 移动的总次数不超过 n 次

总操作次数：O(2n) = O(n)

为什么是 O(n) 而不是 O(n²)？

每个字符最多被：
1. 右指针访问一次（加入集合）
2. 左指针访问一次（从集合删除）

所以总共最多 2n 次操作，即 O(n)

空间复杂度：O(min(n, m))

charSet 存储窗口中的字符
窗口大小 ≤ min(n, 字符集大小)

英文字符集：最多 26 个字母 → O(26) = O(1)
ASCII 字符集：最多 128 个字符 → O(128) = O(1)
Unicode：可能更多，但一般还是 O(字符集大小)

但题目通常限制为英文字母、数字、符号等，所以可以认为是 O(1)
更准确地说：O(min(n, 字符集大小))

代码

class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 使用哈希集合存储当前窗口中的字符（用于快速判断重复）
unordered_set<char> charSet;

int n = s.size(); // 字符串长度
int ans = 0; // 最长无重复子串的长度

// 滑动窗口：左指针l，右指针r
// 外层循环：右指针不断向右扩展
for (int left = 0, right = 0; right < n; right++) {

// 关键：如果当前字符 s[right] 已经在集合中
// 说明出现了重复，需要收缩窗口
while (charSet.find(s[right]) != charSet.end()) {
// 从集合中移除左指针指向的字符
// 左指针向右移动，直到移除掉那个重复的字符
charSet.erase(s[left]);
left++; // 左指针右移
}

// 将当前字符加入集合（现在集合中没有重复了）
charSet.insert(s[right]);

// 计算当前窗口的大小（无重复子串的长度）
int currentLength = charSet.size();

// 更新最大长度
ans = max(ans, currentLength);

// 也可以这样计算：ans = max(ans, right – left + 1);
}

return ans;
}
};