上期回顾
在之前的滑动窗口练习中，我们处理过类似最小覆盖子串的问题。滑动窗口的核心套路其实相对固定，关键在于如何维护窗口内的状态。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int left = 0, right = 0, length = n + 1, sum = 0;
while (right < nums.size()) {
sum += nums[right];
while (sum >= target) {
length = min(right - left + 1, length);
sum -= nums[left++];
}
right++;
}
return length == n + 1 ? 0 : length;
}
};
本期题目：无重复字符的最长子串
问题描述
给定一个字符串 s，请你找出其中不含有重复字符的 最长子串 的长度。
关键点分析
- 无重复：窗口内字符不能重复出现。
- 统计频次：需要知道每个字符出现的次数（使用哈希表）。
- 最长：目标是最大化窗口长度。
- 子串：必须是连续的，不能跳跃。
暴力解法
最直观的思路是枚举所有可能的子串，检查是否包含重复字符。
双重循环 + 哈希表统计
外层循环确定起点，内层循环扩展终点。每次进入新的起点时，重置哈希表重新统计。如果发现重复字符，立即停止当前起点的遍历。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.size(), ret = 0;
for (int i = 0; i < n; i++) {
int hash[128] = {0}; // 使用数组模拟哈希表，每次外循环刷新
for (int j = i; j < n; j++) {
hash[s[j]]++;
if (hash[s[j]] > 1) {
ret = max(ret, j - i);
break; // 有重复字符的情况
}
}
ret = max(ret, j - i); // 处理无重复字符的情况
}
return ret;
}
};
时间复杂度为 $O(N^2)$。虽然能通过部分测试用例，但存在明显的性能瓶颈：每次遇到重复字符后，我们放弃了当前的统计结果，下一次遍历时又重新计算了一遍之前已经统计过的数据。
优化思路：滑动窗口
既然暴力解法浪费了大量重复计算的资源，我们可以尝试对之前的统计数据进行维护，而不是每次都从头开始。
观察发现，当右指针向右移动遇到重复字符时，我们不需要把整个窗口清空，只需要将左指针向右移动，直到移除导致重复的那个字符即可。这就是典型的同向双指针模型，也就是滑动窗口。
通过这种机制，每个字符最多被访问两次（一次进窗口，一次出窗口），时间复杂度可以优化到 $O(N)$。
算法逻辑
- 初始化：定义左右指针
left,right，以及用于计数的数组hash[128]。 - 进窗口：右指针向右移动，将字符加入计数。
- 条件判断：如果某字符计数大于 1，说明出现重复，开始收缩窗口。
- 出窗口：左指针向右移动，减少对应字符的计数，直到重复消除。
- 更新结果：每次窗口合法时，更新最大长度。
代码实现
下面直接上优化后的 C++ 实现，注意数组模拟哈希表的细节。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.size();
int hash[128] = {0}; // ASCII 码范围足够用 128 大小的数组
int left = 0, right = 0, ret = 0;
while (right < n) {
// 进窗口：统计当前字符
hash[s[right]]++;
// 如果当前字符重复，收缩左边界
while (hash[s[right]] > 1) {
hash[s[left]]--;
left++;
}
// 更新最大长度
ret = max(ret, right - left + 1);
right++;
}
return ret;
}
};
总结
这道题是滑动窗口的经典应用。相比于暴力解法，优化的关键在于动态维护窗口状态。只要理解了'右扩左缩'的逻辑，这类题目就能迎刃而解。