（8）LeetCode 3. 无重复字符的最长子串

LeetCode 3. 无重复字符的最长子串 题目描述给定一个字符串s请你找出其中不含有重复字符的最长子串的长度。示例输入: s abcabcbb 输出: 3 解释: 因为无重复字符的最长子串是 abc所以其长度为 3。 解题思路本题是经典的滑动窗口问题。核心思想维护一个动态窗口保证窗口内的字符都不重复并不断更新窗口的最大长度。使用两个指针i窗口右边界和j窗口左边界来滑动窗口。使用一个哈希表unordered_mapchar, int记录当前窗口中每个字符出现的次数。当右指针i遍历字符时将该字符加入窗口哈希表计数1。如果加入后该字符的计数大于 1说明窗口内出现了重复字符此时需要移动左指针j将s[j]移出窗口计数-1并右移j直到重复字符的计数恢复为 1。每调整完一次窗口当前窗口[j, i]就是一个无重复子串其长度为i - j 1更新答案ans为最大值。这样我们遍历完所有可能的右端点就能得到全局最长无重复子串的长度。 代码实现CclassSolution{public:intlengthOfLongestSubstring(string s){unordered_mapchar,inthash;// 哈希表记录窗口内字符出现次数intans0;// 保存最长无重复子串的长度for(inti0,j0;is.size();i){hash[s[i]];// 将当前字符加入窗口while(hash[s[i]]1)// 如果当前字符出现次数 1说明有重复hash[s[j]]--;// 移动左边界直到重复消除ansmax(ans,i-j1);// 更新答案}returnans;}}; 代码逐句解释unordered_mapchar, int hash;哈希表键为字符值为该字符在当前窗口中出现的次数。int ans 0;用于存储当前找到的最大长度。for(int i 0, j 0; i s.size(); i)i作为右指针遍历整个字符串j作为左指针维护窗口左边界。hash[s[i]] ;将右指针指向的字符加入窗口计数1。while(hash[s[i]] 1)如果刚刚加入的字符s[i]在窗口中出现次数大于 1说明窗口内已有该字符出现了重复。注意这里的判断条件是hash[s[i]] 1因为只有新加入的字符才有可能导致重复我们只需要消除由它引起的重复即可。hash[s[j]]--;将左指针j指向的字符移出窗口计数-1并将j右移一位。重复此过程直到s[i]的计数变为 1即窗口不再包含重复字符。ans max(ans, i - j 1);当前窗口[j, i]是一个合法的无重复子串用其长度更新答案。 示例演示以s abcabcbb为例模拟过程i (右指针)当前字符窗口内容 (j ~ i)hash 状态 (出现次数)是否有重复调整后窗口长度ans0aaa:1无a111baba:1, b:1无ab222cabca:1, b:1, c:1无abc333aabcaa:2, b:1, c:1有 (a重复)移动j至bca334bbcabb:2, c:1, a:1有 (b重复)移动j至cab335ccabcc:2, a:1, b:1有 (c重复)移动j至abc336babcba:1, b:2, c:1有 (b重复)移动j至cb237bcbbc:1, b:2有 (b重复)移动j至b13最终结果为 3。⏱ 复杂度分析时间复杂度O(n)其中 n 是字符串长度。左指针j和右指针i分别最多移动 n 次每个字符进入和离开哈希表各一次因此总操作次数为 2n复杂度 O(n)。空间复杂度O(∣Σ∣)其中 Σ 是字符集ASCII 字符、Unicode 等。哈希表最多存储字符集大小的键值对可以认为是 O(1) 级别因为字符集大小固定。 总结本题使用滑动窗口 哈希表完美解决了“子串无重复”的约束。关键在于利用哈希表快速判断重复并通过移动左边界动态调整窗口。这种思想也适用于其他“连续子区间”问题如“最多包含 k 个不同字符的最长子串”等只需稍作修改即可。