算法题打卡力扣第3题：无重复字符的最长子串(mid)

题目描述

解法一：暴力解

遍历每一个可能的子串，然后逐一判断每个子串中是否有重复字符。

具体步骤：

• 使用两层嵌套循环来生成所有子串的起止位置：
  外层循环 i 从 0 到 n-1 (起始位置)。
  内层循环 j 从 i 到 n-1 (结束位置)。
• 对于每一个子串 s.substring(i, j+1)，我们再设计一个辅助函数 hasDuplicate(substring) 来检查这个子串中是否存在重复字符。
• 检查 hasDuplicate 通常需要使用一个哈希集合 (Set)：遍历子串的每个字符，尝试加入 Set。如果某个字符加入失败（因为 Set 中已存在），则说明有重复。
• 如果没有重复，我们就用 j - i + 1 来更新记录的最大长度 max_len。

实现代码

#include <unordered_set> // 用于哈希集合
#include <algorithm>     // 用于 std::max
class Solution {
public:int lengthOfLongestSubstring(string s) {int n = s.length();int max_len = 0;for(int i=0;i<n;++i){for(int j=i;j<n;++j){std::string substring = s.substr(i,j-i+1);if(!hasDuplicate(substring)){max_len = std::max(max_len,(int)substring.length());}}}return max_len;}bool hasDuplicate(const std::string&s){std::unordered_set<char> seen_characters;for(char c : s){if(!seen_characters.insert(c).second){return true;}}return false;}
};

执行结果
超出时间范围了

复杂度分析
时间：O(n^3)
空间：O(n)

解法二：滑动窗口

我们维护一个窗口 [start, end]，它始终代表一个不包含重复字符的子串。我们不断尝试扩大这个窗口的右边界end。如果在这个过程中，新加入的字符导致了窗口内出现重复，我们就需要收缩窗口的左边界 start，直到窗口内不再有重复字符为止。

如何快速判断字符是否重复以及其位置？
我们需要一个数据结构来高效地完成两件事：
判断一个字符是否已经在当前窗口中。
如果存在，找出它上次出现的位置。
哈希映射 (Map) 或数组是完美的选择。
哈希映射 Map<Character, Integer>：键 (Key) 存储字符，值 (Value) 存储该字符的最新索引。
数组 int[128]：如果字符集是 ASCII，我们可以用一个大小为 128 的数组来模拟哈希映射，数组的索引是字符的 ASCII 码，值是该字符的最新索引。这比哈希映射更快。

具体步骤 (以哈希映射为例)：
初始化两个指针：start = 0 (窗口左边界)，end = 0 (窗口右边界)。
初始化 max_len = 0 (记录最大长度)。
初始化一个哈希映射 map，用于存储窗口内字符及其最新索引。
使用 end 指针作为主循环，从 0 遍历到 n-1：
a. 获取当前右边界的字符 char_end = s[end]。
b. 检查 char_end 是否导致重复：
i. 在 map 中查找 char_end。
ii. 如果 char_end 已经在 map 中存在，并且它上次出现的位置 map.get(char_end) 在当前窗口内（即 map.get(char_end) >= start），这说明我们遇到了一个重复字符。
iii. 为了消除这个重复，我们需要将窗口的左边界 start 跳跃到重复字符的下一个位置。即 start = map.get(char_end) + 1。
c. 更新 map：无论是否重复，我们都需要更新 char_end 在 map 中的位置为当前的 end 索引。map.put(char_end, end)。
d. 更新 max_len：在每一步之后，当前有效的无重复子串的长度就是 end - start + 1。我们用它来更新 max_len。 max_len = max(max_len, end - start + 1)。
e. end 指针自增，考察下一个字符。
循环结束后，max_len 就是最终答案。
实现代码

class Solution {
public:int lengthOfLongestSubstring(string s) {int n = s.length();if(n==0){return 0;}std::unordered_map<char,int> char_map;int max_len = 0;int start = 0;for(int end = 0;end<n;++end){char current_char = s[end];if(char_map.count(current_char)&&char_map[current_char] >= start){start = char_map[current_char] + 1;}char_map[current_char] = end;max_len = std::max(max_len,end-start+1);}return max_len;}};

执行结果

复杂度分析
时间：O
空间：O