滑动窗口的关键不是“枚举所有区间”,而是让右端 i 负责扩张,让左端 j 只在出现重复时才收缩。每个元素最多进窗口一次、出窗口一次,所以总复杂度是 O(n)。
还没有读入任何元素,窗口为空,准备让右指针 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);
}