每日一练 找无重复字符的最长子串

我们来看下这个题目，我们要统计的是不重复的子串，我们可以使用“滑动窗口法”，其实我们很容易就能想到思路。

我们的左窗代表我们目前遍历的开始，即我们遍历的子串的开头，右窗从左窗开始进行遍历，每次遍历都把当前的字符放入组内，遇到重复则退出计算此时的子串长度，接下来左窗加1继续遍历。在java中，我们可以用hashset来做这种重复筛查。

下面是代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int length = s.length() ;
        int ans = 0 ;
        for(int i = 0 ; i < length ; i++ ){
            Set<Character> chachong = new HashSet<Character>() ;
            int r = i  ;
            chachong.add(s.charAt(i)) ;
            while( r+1 < length && !chachong.contains(s.charAt(r+1))){
                chachong.add(s.charAt(r+1)) ;
                r++ ;
            }
            ans = Math.max(r-i+1 , ans);
        }
        return ans ;
    }
}

思路清晰，但是我们每次滑动左窗都要重新建立我们的hashset，这样显然有些麻烦而且我们的空间复杂度也比较大，那么有什么可以修改的地方呢？

显然，我们可以把整个hashset放在外面，那样我们只需把左窗的字符退出hashset，然后接着右窗遍历就可以了，思路是这样但是实际如何呢？接下来看代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int length = s.length() ;
        int ans = 0 ;
        int r = 0  ;
        Set<Character> chachong = new HashSet<Character>() ;
        for(int i = 0 ; i < length ; i++ ){
            chachong.add(s.charAt(i)) ;
            while( r+1 < length && !chachong.contains(s.charAt(r+1))){
                chachong.add(s.charAt(r+1)) ;
                r++ ;
            }
            ans = Math.max(r-i+1 , ans) ;
            chachong.remove(s.charAt(i)) ;
        }
        return ans ;
    }
}

 实际上我们的运行结果是有问题的：

在此样例中，我们就不能通过。问题出在当我们的右窗无法重置位置，就有可能出现右窗在左窗左边的情况，在这种情况下，我们如何能让右窗重新“归位”，保证右窗与左窗的联系呢？实际上，我们把退出左窗放在下一次循环里，循环中我们开始便退出上一次的左窗，这样的话我们可以发现，我们的右窗会保证跟在左窗后最终实现归位。 

最终代码如下：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int length = s.length() ;
        int ans = 0 ;
        int r = 0  ;
        Set<Character> chachong = new HashSet<Character>() ;
        for(int i = 0 ; i < length ; i++ ){
            chachong.add(s.charAt(i)) ;
            if(i!=0){
                chachong.remove(s.charAt(i-1)) ;
            }
            while( r+1 < length && !chachong.contains(s.charAt(r+1))){
                chachong.add(s.charAt(r+1)) ;
                r++ ;
            }
            ans = Math.max(r-i+1 , ans) ;
        }
        return ans ;
    }
}