滑动窗口算法：无重复字符的最长子串（数组模拟哈希表）

上期参考代码

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;
    }
};

本期题目

无重复字符的最长子串

读题

要点

• 无重复
• 需要统计元素出现的次数（哈希表）
• 最长
• 子串（必须是连续的，示例三已强调）

解题

暴力解法

双重循环遍历元素 + 哈希表统计元素出现次数

在遍历元素的过程中，将元素扔进哈希表统计它出现的次数，内层如果遍历到的元素出现次数大于 1，直接跳过接下来的遍历过程，外循环开始下一次遍历。

代码：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size(), ret = 0;
        int i, j;
        for (i = 0; i < n; i++) {
            int hash[128] = {0}; // 使用数组来模拟哈希表，每次外循环刷新
            for (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)，能过，但是还能优化。

优解

摸索

分析上述暴力解法，我们发现，每次统计数据的时候我们都要刷新哈希表，然后重新统计，之前统计的数据有部分还是需要重新再统计一遍，资源大大浪费，我们可以尝试找到一种方法，对之前的统计数据进行维护，提高代码效率。

我们先用双指针来模拟并改进暴力解法：

通过模拟我们发现，双指针可灵活维护统计数据，且双指针是同向移动的，同向双指针，也就是我们的滑动窗口，可以直接把嵌套 for 的 N^2 时间复杂度干成 N。

发现了同向双指针，我们就可以使用滑动窗口的固定套路来写代码啦

代码逻辑

1. 初始化双指针
2. 进窗口：把元素扔进哈希表统计出现次数
3. 条件判断：出现次数>1，开始出窗口
4. 更新结果：出完窗口之后，子串一定是符合条件的，此时更新 ret

代码：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        int left = 0, right = 0, ret = 0;
        int hash[128] = {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;
    }
};

下期预告

最大连续 1 的个数 III