LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 使用两个变量 l 和 r 来表示子串范围（包含 s[l] 和 s[r]），这个范围视为一个窗口，窗口宽度即为子串长度
• 初始化时，l 和 r 均为 0，指向开头的同一字符，此时窗口中无重复字符
• 逐次右移右边界，每次右移时，如果窗口不含右边界的范围中存在与右边界相同的值，则将左边界移动到重复值的下一位置，这样即可保持窗口中无重复元素。窗口滑动过程中的宽度 r - l + 1 的最大值即为结果

abcabcbb
01234567

l = 0, r = 0 a
l = 0, r = 1 ab => a 与 b 比较，无重复，不更新左边界
l = 0, r = 2 abc => ab 与 c 比较，无重复，不更新左边界
l = 0, r = 3 abca => abc 与 a 比较，a重复，更新左边界
l = 1, r = 3 bca
l = 1, r = 4 bcab => bca 与 b 比较，b 重复，更新左边界
l = 2, r = 4 cab
l = 2, r = 5 cabc => cab 与 c 比较，c 重复，更新左边界
l = 3, r = 5 abc
l = 3, r = 6 abcb => abc 与 b 比较，b 重复，更新左边界
l = 5, r = 6 cb
l = 5, r = 7 cbb => cb 与 b 比较，b 重复，更新左边界
l = 7, r = 7 b
l = 7, r = 8 r 越界，结束移动

上述过程中窗口无重复元素时，最大宽度为 3，结果即为 3

• 实现如下

class Solution {
 public:
  int lengthOfLongestSubstring(string s) {
    int res = 0;
    int l = 0;
    for (int r = 0; r < size(s); ++r) {
      for (int i = l; i < r; ++i) {
        if (s[i] == s[r]) {
          l = i + 1;
          break;  // 后续不会再有重复值，可以提前结束此轮比较
        }
      }
      res = max(res, r - l + 1);
    }
    return res;
  }
};