本篇博客是一篇滑动窗口算法练习题——无重复字符的最长子串的思路详解，从最开始的暴力解法，优化以及怎么想到滑动窗口这种算法的一个详细思路过程，有需要借鉴即可。
1.题目解读
题目链接：LINK
读了题目我大概就抓住了两个要点，一是长度最长，而是得连续。
闭着眼都知道，我第一步首先肯定想到的是硬解，也就是我们常说的“暴力求解”。
2.暴力求解
思路：用left和right两个指针依次枚举所有可能情况，利用哈希表看是否满足条件即可。
时间复杂度：O(N^2)
但是这种方法，很挫，效率太低了。
3.暴力求解的优化
为了提高效率，我们可以利用滑动窗口的思路。
怎么想到滑动窗口的呢？
- 优化一：当结果不合法时，需要left右移，干掉重复的字符
- 优化二：当结果再次合法时，不需要right回到最初位置，直接在原位置向前走即可
- 优化三：利用哈希数组代替哈希表，提高效率，节约空间
这两点优化指明：满足滑动窗口双指针同向不会退的特点，因而想到了滑动窗口算法
4.题解代码示例
class Solution { public: int lengthOfLongestSubstring(string s) { int hash[128] = {0};//数组模拟哈希表 int left = 0,right = 0,n = s.size(),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; } };
EOF
