20.12.29 leetcode3

题目链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

题意：给你一个字符串，求不包含重复字符的最长子串。

分析：我们观察以每个字符开头的不包含重复字符的最长子串，可以发现随着开始字符的递增，结束字符也在递增，这点很好理解。

所以用集合来存储目前有多少字符，从左到右遍历每个开始字符，而结束字符的位置和结合是不需要每次重置的，这样时间复杂度只有O(N)

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