1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution
{
 public:
  int lengthOfLongestSubstring(string s)
  {
    /** 
     *    记录元素最后一次出现的位置，用于判断r指向的字符是否已经在当前窗口已经存在
     *    以及帮助 l 指针进行移动
     */
    unordered_map<char, int> hash; 
    int ans, l, r;
    for (l = r = ans = 0; r < s.size(); ++r)
    {
      // 判断当前窗口是否存在重复字符
      // 需要注意的是 hash[s[r]] >= l，这样才能确保当前元素是存在于当前窗口的
      // 若没有这个条件，只能说明 s[r] 字符在前面出现过，但不能确保它是在当前窗口中的
      // 比如 abba 字符串，当我们的窗口内字符为 ba 时，hash[s[3]] 的值为 0 但其并不在当前窗口内
      if (hash.find(s[r]) != hash.end() && hash[s[r]] >= l)
      {
        ans = max(ans, r - l);
        l = hash[s[r]] + 1; // 将重复的字符串移除窗口
      }

      // 更新字符最后一次出现的下标
      hash[s[r]] = r;
    }

    // r - l 计算最后一个窗口的长度
    return max(ans, r - l);
  }
};