[滑动窗口] 10. 无重复字符的最长子串

一. 题目描述二. 解题思路1. 暴力解法就是枚举所有子数组将子数组中的字符放入一个哈希表统计出现次数有重复则不符合。找出剩余的没有重复的最长的子数组。2. 因为right指针定位的是重复的第二个元素所以第一个重复元素及之前的元素到right位置的区间内都会有重复left直接跳过第一个重复值。3. left跳过重复值之后left到right之间一定没有重复值。所以right也不用退回到left的位置重新遍历所以left和right都是持续向右遍历同向双指针即为滑动窗口。4.滑动窗口实现思路① 先定义双指针left 0right 0② right指针控制进窗口就是让字符进入哈希表③ 判断窗口内是否出现的重复元素若出现了持续出窗口就是从哈希表中删除该字符直到left跳过了重复元素即判断是否重复的条件不成立了④ 若没出现重复更新结果取当前长度和之前最长长度的较大值⑤ 结束条件right走到头了三. 代码实现class Solution { public: int lengthOfLongestSubstring(string s) { // 用ASCII码做下标无冲突哈希表 size_t left 0, right 0, len 0; vectorint hash(128); while(right s.size()) { // 进窗口进一个我就判断一下是否重复 hash[s[right]]; // 判断 while(hash[s[right]] 1) { // 重复了出窗口:从哈希表中删除left指向的内容并left // 直到left跳过重复字符 hash[s[left]]--; } // 没重复 right; len max(len, right - left); } return len; } };