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

一. 题目描述

二. 解题思路

1. 暴力解法就是枚举所有子数组，将子数组中的字符放入一个哈希表统计出现次数，有重复则不符合。找出剩余的没有重复的最长的子数组。

2. 因为right指针定位的是重复的第二个元素，所以第一个重复元素及之前的元素到right位置的区间内都会有重复，left直接跳过第一个重复值。

3. left跳过重复值之后，left到right之间一定没有重复值。所以right也不用退回到left的位置重新遍历，所以left和right都是持续向右遍历，同向双指针即为滑动窗口。

4.滑动窗口实现思路：

① 先定义双指针：left = 0，right = 0；

② right指针控制进窗口（就是让字符进入哈希表）

③ 判断窗口内是否出现的重复元素，若出现了持续出窗口（就是从哈希表中删除该字符）直到left跳过了重复元素（即判断是否重复的条件不成立了）

④ 若没出现重复，更新结果（取当前长度和之前最长长度的较大值）

⑤ 结束条件：right走到头了

三. 代码实现

class Solution { public: int lengthOfLongestSubstring(string s) { // 用ASCII码做下标，无冲突哈希表 size_t left = 0, right = 0, len = 0; vector<int> 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; } };