Leetcode力扣解题记录--第3题（滑动窗口）

题目链接：3. 无重复字符的最长子串 - 力扣（LeetCode）

题目描述

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

0 <= s.length <= 5 * 104

s 由英文字母、数字、符号和空格组成

题目作答

这个问题的目标是找到一个最长的连续子串，该子串中没有重复的字符。我们可以把思路想象成一个“窗口”在字符串上滑动。

1. 滑动窗口思想

• 我们用两个指针，left 和 right，来表示一个“窗口”，窗口内的子串 s[left...right] 是我们当前正在考察的无重复字符的子串。
• right 指针负责向右移动，不断扩大窗口，把新的字符包含进来。
• left 指针负责在窗口内出现重复字符时，向右移动，以缩小窗口，使得窗口内不再有重复字符。

2. 如何高效判断重复？

• 当我们把新字符 s[right] 加入窗口时，需要快速判断它是否已经在窗口 s[left...right-1] 中存在了。
• 使用一个哈希表（在C++ 中可以利用 std::unordered_map）是解决这个问题的核心工具。我们可以用它来存储字符和它最近一次出现的位置索引。

3. 算法步骤

1. 初始化一个哈希表 map 用于存储字符及其索引，一个 left 指针表示窗口的左边界，初始为 0，一个 max_len 变量记录最大长度，初始为 0。
2. 用 right 指针从 0 到 s.length() - 1 遍历整个字符串，这个 right 指针代表窗口的右边界。
3. 对于每个 right 指针指向的字符 c = s[right]：
   • 检查重复：在哈希表 map 中查找是否存在字符 c。
   • 如果 c 存在，并且它上一次出现的位置 map[c] 大于等于当前窗口的左边界 left（即 map[c] >= left），说明字符 c 在当前窗口内重复了。
   • 处理重复：为了保证窗口内没有重复字符，我们必须将窗口的左边界 left 移动到重复字符上一次出现位置的下一个位置。即 left = map[c] + 1。
4. 更新信息：
   • 无论是否重复，我们都需要更新哈希表中字符 c 的位置为当前的 right 索引，以保证存储的是它最近一次出现的位置。即 map[c] = right。
   • 计算当前无重复窗口的长度 right - left + 1，并用它来更新 max_len。max_len = max(max_len, right - left + 1)。
5. 遍历结束后，max_len 就是最终的结果。

举例说明: s = "abcabcbb"

• r=0, c='a': map={'a':0}, len=1, max_len=1, left=0
• r=1, c='b': map={'a':0, 'b':1}, len=2, max_len=2, left=0
• r=2, c='c': map={'a':0, 'b':1, 'c':2}, len=3, max_len=3, left=0
• r=3, c='a': 发现 'a' 已存在于 map 中，其位置 0 >= left(0)。窗口内重复。
  • 移动 left 到 map['a'] + 1，即 left = 0 + 1 = 1。
  • 更新 map={'a':3, 'b':1, 'c':2}。
  • 当前窗口为 s[1...3] ("bca")，长度为 3-1+1=3。max_len 仍为 3。
• ...以此类推，直到遍历结束。

s = " a  b  c  a  b  c  b  b "

i  = " 0  1  2  3  4  5  6  7 "

步骤 (r)	当前字符	操作/判断	left 指针	当前窗口	窗口长度	max_len	哈希表 (map) 状态
0	'a'	添加新字符	0	"a"	1	1	{'a':0}
1	'b'	添加新字符	0	"ab"	2	2	{'a':0, 'b':1}
2	'c'	添加新字符	0	"abc"	3	3	{'a':0, 'b':1, 'c':2}
3	'a'	发现重复 'a'，移动 left 至 map['a']+1	1	"bca"	3	3	{'a':3, 'b':1, 'c':2}
4	'b'	发现重复 'b'，移动 left 至 map['b']+1	2	"cab"	3	3	{'a':3, 'b':4, 'c':2}
5	'c'	发现重复 'c'，移动 left 至 map['c']+1	3	"abc"	3	3	{'a':3, 'b':4, 'c':5}
6	'b'	发现重复 'b'，移动 left 至 map['b']+1	5	"cb"	2	3	{'a':3, 'b':6, 'c':5}
7	'b'	发现重复 'b'，移动 left 至 map['b']+1	7	"b"	1	3	{'a':3, 'b':7, 'c':5}

class Solution {
public:int lengthOfLongestSubstring(string s) {// 哈希表，用于存储字符及其最近一次出现的索引// Key: 字符, Value: 索引unordered_map<char, int> char_map;int max_len = 0; // 用于记录最长子串的长度int left = 0;    // 滑动窗口的左边界// right 是滑动窗口的右边界for (int right = 0; right < s.length(); ++right) {char current_char = s[right];// 检查当前字符是否在哈希表中已存在，并且其索引在当前窗口内if (char_map.count(current_char) && char_map[current_char] >= left) {// 如果是，则发生了重复。// 将窗口的左边界移动到重复字符上一次出现位置的下一个位置。left = char_map[current_char] + 1;}// 更新当前字符的最新位置索引char_map[current_char] = right;// 计算当前窗口的长度，并更新最大长度记录max_len = max(max_len, right - left + 1);}return max_len;}
};