LeetCode 力扣 热题 100道（三）无重复字符的最长子串（C++）

无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
（子字符串 是字符串中连续的 非空 字符序列）

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> char_set; 
        int left = 0;  
        int max_len = 0; 
        for (int right = 0; right < s.size(); ++right) {
            while (char_set.find(s[right]) != char_set.end()) {
                char_set.erase(s[left]);
                left++;
            }
            char_set.insert(s[right]);
            max_len = max(max_len, right - left + 1);
        }
        return max_len;
    }
};

我们来针对输入 "abcabcbb"这个测试用例来讲解，如下所示：

初始化

• char_set: 是一个 unordered_set，用于存储当前窗口内的字符，确保窗口内的字符是唯一的。
• left: 左指针，初始值为 0，表示窗口的左边界。
• max_len: 用于记录最长无重复子串的长度，初始值为 0。

遍历字符串

我们通过 right 指针从左到右遍历字符串 s，并不断更新 max_len。

输入字符串为 "abcabcbb"，其长度为 8。我们按每次循环逐步分析。

第 1 次循环 (right = 0)

• 当前字符 s[right] = 'a'。
• 检查 char_set 是否包含 'a'，char_set.find('a') 返回 char_set.end()，说明没有重复字符。
• 将 'a' 插入到 char_set 中：char_set = {'a'}。
• 计算当前窗口的长度 right - left + 1 = 0 - 0 + 1 = 1，更新 max_len = max(0, 1) = 1。

第 2 次循环 (right = 1)

• 当前字符 s[right] = 'b'。
• 检查 char_set 是否包含 'b'，char_set.find('b') 返回 char_set.end()，说明没有重复字符。
• 将 'b' 插入到 char_set 中：char_set = {'a', 'b'}。
• 计算当前窗口的长度 right - left + 1 = 1 - 0 + 1 = 2，更新 max_len = max(1, 2) = 2。

第 3 次循环 (right = 2)

• 当前字符 s[right] = 'c'。
• 检查 char_set 是否包含 'c'，char_set.find('c') 返回 char_set.end()，说明没有重复字符。
• 将 'c' 插入到 char_set 中：char_set = {'a', 'b', 'c'}。
• 计算当前窗口的长度 right - left + 1 = 2 - 0 + 1 = 3，更新 max_len = max(2, 3) = 3。

第 4 次循环 (right = 3)

• 当前字符 s[right] = 'a'。
• 检查 char_set 是否包含 'a'，char_set.find('a') 返回非 char_set.end()，说明有重复字符。
• 进入 while 循环，开始调整窗口的左边界 left：
  • 移除 s[left] = 'a' 从 char_set 中：char_set = {'b', 'c'}。
  • 左指针右移：left = 1。
  • 继续检查 char_set 是否包含 'a'，此时不再包含 'a'。
• 将 'a' 插入到 char_set 中：char_set = {'b', 'c', 'a'}。
• 计算当前窗口的长度 right - left + 1 = 3 - 1 + 1 = 3，max_len 不变，仍为 3。

第 5 次循环 (right = 4)

• 当前字符 s[right] = 'b'。
• 检查 char_set 是否包含 'b'，char_set.find('b') 返回非 char_set.end()，说明有重复字符。
• 进入 while 循环，开始调整窗口的左边界 left：
  • 移除 s[left] = 'b' 从 char_set 中：char_set = {'c', 'a'}。
  • 左指针右移：left = 2。
  • 继续检查 char_set 是否包含 'b'，此时不再包含 'b'。
• 将 'b' 插入到 char_set 中：char_set = {'c', 'a', 'b'}。
• 计算当前窗口的长度 right - left + 1 = 4 - 2 + 1 = 3，max_len 不变，仍为 3。

第 6 次循环 (right = 5)

• 当前字符 s[right] = 'c'。
• 检查 char_set 是否包含 'c'，char_set.find('c') 返回非 char_set.end()，说明有重复字符。
• 进入 while 循环，开始调整窗口的左边界 left：
  • 移除 s[left] = 'c' 从 char_set 中：char_set = {'a', 'b'}。
  • 左指针右移：left = 3。
  • 继续检查 char_set 是否包含 'c'，此时不再包含 'c'。
• 将 'c' 插入到 char_set 中：char_set = {'a', 'b', 'c'}。
• 计算当前窗口的长度 right - left + 1 = 5 - 3 + 1 = 3，max_len 不变，仍为 3。

第 7 次循环 (right = 6)

• 当前字符 s[right] = 'b'。
• 检查 char_set 是否包含 'b'，char_set.find('b') 返回非 char_set.end()，说明有重复字符。
• 进入 while 循环，开始调整窗口的左边界 left：
  • 移除 s[left] = 'a' 从 char_set 中：char_set = {'b', 'c'}。
  • 左指针右移：left = 4。
  • 继续检查 char_set 是否包含 'b'，此时不再包含 'b'。
• 将 'b' 插入到 char_set 中：char_set = {'b', 'c'}。
• 计算当前窗口的长度 right - left + 1 = 6 - 4 + 1 = 3，max_len 不变，仍为 3。

第 8 次循环 (right = 7)

• 当前字符 s[right] = 'b'。
• 检查 char_set 是否包含 'b'，char_set.find('b') 返回非 char_set.end()，说明有重复字符。
• 进入 while 循环，开始调整窗口的左边界 left：
  • 移除 s[left] = 'b' 从 char_set 中：char_set = {'c'}。
  • 左指针右移：left = 5。
  • 继续检查 char_set 是否包含 'b'，此时不再包含 'b'。
• 将 'b' 插入到 char_set 中：char_set = {'c', 'b'}。
• 计算当前窗口的长度 right - left + 1 = 7 - 5 + 1 = 3，max_len 不变，仍为 3。

原文地址：https://blog.csdn.net/weixin_64593595/article/details/143730478

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！