3. 无重复的最长子串
题目看起来简单，刷起来有好几个坑，特此记录一下，解法比官网的更加简单，可读性强。时间复杂度与空间复杂度与官方一样。
问题描述
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1:
示例 2:
示例 3:
提示：
- 0 <= s.length <= 5 * 1 0 4 10^4 104；
s由英文字母、数字、符号和空格组成。
问题分析
解决方法
结合示例 1，我做了一个详细的双指针移动 PPT 示意图。
解题代码
请小伙伴们结合上面的PPT进行理解，以下内容包括两种方法，第一种是基于哈希表，第二种使用 vector 替代哈希表，更快更节省资源（时间复杂度不变）
方法一：基于 unordered_map 记录历史 + 双指针一次遍历
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 用于记录每个字符最后一次出现的索引
unordered_map<char, int> map;
// 最终结果
int result = 0;
// 指针的开始位置，我们最终要求的无重复字符的最长子串的开始位置
// 这个指针将会根据实际情况而移动，方向是一直向右
int start = 0;
// 一次遍历所有字符
// 遍历过程中主要处理两个事情
// 1. 移动 start 指针
// 2. 计算现在已知的最长子串的长度
for (int i = 0; i < s.length(); i++) {
// 查找历史中该点
auto tmp = map.find(s[i]);
// 如果历史中存在数据，需要更新 start 的位置，表示新的最长子串的开始位置
// 需要注意的是，更新后的start 必须越来越大，即向右边移动，避免 start 向左边移动
if (tmp != map.end()) {
start = max(tmp -> second + 1, start);
}
// 更新最后的结果，即最长子串的长度
result = max(result, i - start + 1);
// 写入/更新 s[i] 字符的索引
map[s[i]] = i;
}
return result;
}
};
- 时间复杂度： O ( n ) O(n) O(n)
- 空间复杂度： O ( ∑ ) O(\sum) O(∑)，其中 ∑ \sum ∑ 表示字符集（即字符串中可以出现的字符），∣ ∑ \sum ∑∣ 表示字符集的大小。在本题中没有明确说明字符集，因此可以默认为所有 ASCII 码在 [0,128) 内的字符，即 ∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符，而字符最多有 ∣ ∑ \sum ∑∣ 个，因此空间复杂度为 O(∣ ∑ \sum ∑∣)。
方法二：基于 vector 记录历史 + 双指针一次遍历
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 用于记录每个字符最后一次出现的索引
vector<int> lastIndex(256, -1);
// 最终结果
int result = 0;
// 指针的开始位置，我们最终要求的无重复字符的最长子串的开始位置
int start = 0;
// 一次遍历所有字符
for (int end = 0; end < s.length(); end++) {
// 更新 start 的位置
if (lastIndex[s[end]] != -1) {
start = max(lastIndex[s[end]] + 1, start);
}
// 更新最后的结果，即最长子串的长度
result = max(result, end - start + 1);
// 更新 s[end] 字符的索引
lastIndex[s[end]] = end;
}
return result;
}
};
- 时间复杂度： O ( n ) O(n) O(n)
- 空间复杂度： O ( ∑ ) O(\sum) O(∑)，其中 ∑ \sum ∑ 表示字符集（即字符串中可以出现的字符），∣ ∑ \sum ∑∣ 表示字符集的大小。在本题中没有明确说明字符集，因此可以默认为所有 ASCII 码在 [0,128) 内的字符，即 ∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符，而字符最多有 ∣ ∑ \sum ∑∣ 个，因此空间复杂度为 O(∣ ∑ \sum ∑∣)。
总结
这道题目通过简单的双指针和哈希表的结合，可以高效地解决字符串中无重复字符的最长子串问题。这种方法的时间复杂度为O(n)，因为每个字符在最坏情况下也只会被访问两次（一次作为结束字符，一次作为开始字符）。空间复杂度为O(1)，因为哈希表的大小是固定的，最多为256个字符。
也正是基于这个原因，后面我们增加了使用 vector 提到哈希表，可以更加节省资源以及查找历史的时间。