【子串】3. 无重复的最长子串

3. 无重复的最长子串

难度：中等难度
力扣地址：https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

题目看起来简单，刷起来有好几个坑，特此记录一下，解法比官网的更加简单，可读性强。时间复杂度与空间复杂度与官方一样。

问题描述

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

• 0 <= s.length <= 5 * $10^4$；
• 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(\sum )$，其中 $\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(\sum )$，其中 $\sum$ 表示字符集（即字符串中可以出现的字符），∣$\sum$∣ 表示字符集的大小。在本题中没有明确说明字符集，因此可以默认为所有 ASCII 码在 [0,128) 内的字符，即 ∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符，而字符最多有 ∣$\sum$∣ 个，因此空间复杂度为 O(∣$\sum$∣)。
  

总结

这道题目通过简单的双指针和哈希表的结合，可以高效地解决字符串中无重复字符的最长子串问题。这种方法的时间复杂度为O(n)，因为每个字符在最坏情况下也只会被访问两次（一次作为结束字符，一次作为开始字符）。空间复杂度为O(1)，因为哈希表的大小是固定的，最多为256个字符。

也正是基于这个原因，后面我们增加了使用 vector 提到哈希表，可以更加节省资源以及查找历史的时间。

Smileyan
2024.06.29 22:59