【优选算法】10----无重复字符的最长子串

---------------------------------------begin---------------------------------------

题目解析：

看到这一类题目，有没有那种一眼就感觉时要用到滑动窗口的感觉，铁子们？

讲解算法原理：

方法一:

暴力解法：简单粗暴的地毯式搜索

暴力解法就像一个没有什么技巧的探险家，直接把所有可能的子串都找出来，然后一个一个检查是

不是有重复字符，最后找出最长的那个。虽然有点笨，但好在思路简单，容易理解。不过这方法虽

然简单直接，但效率可不咋地。因为它要检查所有可能的子串，时间复杂度是 O(n^3) ，这里的 n

是字符串的长度。想象一下，如果字符串很长，这探险家得累得够呛，计算量超级大！

方法二：

滑动窗口：聪明探险家的高效寻宝法

滑动窗口就像是给探险家配备了一个高科技的探测仪，能更高效地找到宝藏。它的思路是这样的

用两个指针，一个 left 指针和一个 right 指针，这两个指针就像一个窗口的左右边界。一开始，

left 和 right 都在字符串的开头，然后 right 指针不断向右移动，就像把窗口慢慢扩大，每移动一

次，就把新进来的字符加入到一个集合里，表示这个字符已经被“看到”了。如果发现新进来的字符

已经在集合里了，那就说明出现了重复字符，这时候就把 left 指针向右移动，把窗口左边的字符移

除出集合，直到窗口里没有重复字符为止。在这个过程中，不断更新最长子串的长度。

编写代码：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[128]={0};
        int left=0,right=0,n=s.size();
        int ret=0;
        while(right<n)
        {
            hash[s[right]]++;//入窗口
            while(hash[s[right]]>1)
            {
                hash[s[left++]]--;//出窗口
            }
            ret=max(ret,right-left+1);
            right++;
        }
        return ret;
    }    
};

在这段代码里，while 循环就是滑动窗口的核心操作。right 指针不断向右走，每次遇到一个新字

符，就检查它是不是已经在 hash数组中。如果不在，就把它加入数组，更新最长子串长度，然后

继续向右走；如果在，就把 left 指针向右移动，把窗口左边的字符从集合里移除，直到窗口里没有

重复字符。

滑动窗口的时间复杂度是 O(n) ，因为每个字符最多进窗口和出窗口各一次，比暴力解法不知道快

了多少倍！就好比原来的探险家是徒步在沙漠里找宝藏，现在开着越野车，效率大大提高！