无重复字符的最长子串

 1
 2int lengthOfLongestSubstring(string s)
 3
 4{
 5
 6    int maxStr = 0; // 用来记录出现过的“最长”无重复子串的长度。
 7
 8
 9
10    // 这里的 um (unordered_map) 是核心工具。
11
12    // Key (char): 窗口里的字符
13
14    // Value (int): 这个字符在当前窗口里出现了几次
15
16    std::unordered_map<char, int> um;
17
18
19
20    // 开始滑动窗口。一开始，左右边界都在最左边（索引 0）。
21
22    // right++ 代表窗口的右边缘在不断向右扩展，吞进新的字符。
23
24    for(int left = 0, right = 0; right < s.size(); right++)
25
26    {
27
28        // s[right] 是刚刚进入窗口的新字符。
29
30        // um[s[right]]++ 的意思是：让这个新字符的出现次数 +1。
31
32        um[s[right]]++;
33
34
35
36        // 检查刚刚吞进来的字符，是不是导致窗口里有重复了？
37
38        // 如果 > 1，说明这个字符之前已经在窗口里存在了。
39
40        while(um[s[right]] > 1)
41
42        {
43
44            // 既然有重复了，就缩小窗口：
45
46            // 把最左边的字符 s[left] 踢出窗口，所以它的出现次数 -1。
47
48            um[s[left]]--;
49
50            // 左边界向右移动一格，窗口缩小。
51
52            left++;
53
54        }
55
56
57
58        // 此时认为窗口里已经没有重复字符了。
59
60        // right - left + 1 就是当前窗口的长度。
61
62        // 比如 left=0, right=2，长度就是 2 - 0 + 1 = 3。
63
64        // 用 std::max 更新历史最大长度。
65
66        maxStr = std::max(maxStr, right - left + 1);
67
68    }
69
70    return maxStr; // 遍历完整个字符串，返回找到的最大值。
71
72}