最长不重复数字子串

滑动窗口的关键不是“枚举所有区间”,而是让右端 i 负责扩张,让左端 j 只在出现重复时才收缩。每个元素最多进窗口一次、出窗口一次,所以总复杂度是 O(n)

窗口变化

当前 i-
当前 j-
窗口长度0
最优答案 ans0

开始状态

还没有读入任何元素,窗口为空,准备让右指针 i 从左向右扫过去。

观察重点

  • 窗口内始终保持“没有重复数字”。
  • 右端 i 每次都向右扩张一步。
  • 只有新数字造成重复时,左端 j 才会右移。
  • s[x] 记录数字 x 在当前窗口里出现了几次。
  • ans 只在窗口合法后更新。

对应代码

for (int i = 0, j = 0; i < n; i++) {
    s[a[i]]++;
    while (s[a[i]] > 1) {
        s[a[j]]--;
        j++;
    }
    ans = max(ans, i - j + 1);
}

执行轨迹