无重复字符的最长子串

一、题目

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

二、解答

1.暴力破解

两个for循环把所有子串存入集合，最后找出所有子串中最大值。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length()==0){
            return 0;
        }
        char ss[] = s.toCharArray();
        List<String> list = new ArrayList();
        Set<String> set = new HashSet();
        List<Integer> subList = new ArrayList();
        
        for (int i = 0; i < ss.length; i++) {
            outer:
            for(int j = i;j<ss.length;j++){
                list.add(String.valueOf(ss[j]));
                set.add(String.valueOf(ss[j]));
                if(list.size()>set.size()){
                    subList.add(list.size()-1);
                    list.clear();
                    set.clear();
                    break outer;
                }
            }
        }
        if(subList.size()==0){
            return 1;
        }
        
        int max = subList.get(0);
        for(int k = 0;k<subList.size();k++){
            int cur = subList.get(k);
            if(max<cur){
                max = cur;
            }
        }
        return max;
    }
}

2.滑动窗口

两个变量

• length：当前窗口的长度
• maxLength：窗口的最大长度

存储窗口元素的集合（元素不可重复）：Set

两个指针

• left：左指针

• right：右指针
  左右指针同时从下标0开始，右指针一直往右移动，每次移动到的元素存入窗口元素集合，记录当前长度和最大长度，如果当前长度比最大长度大，则更新最大长度；当遇到当前元素与窗口集合中的元素相同时，移动左指针，同时更新窗口的元素集合（窗口存储的是左右指针之间的元素），直到右指针的元素可以放入窗口集合则左指针停下来，继续移动右指针；如此反复，直到右指针遍历完所有元素，移动过程中记录的最大长度就是最长子串。

  
  最长子串.jpeg

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length()==0){
            return 0;
        }
        int length = 0;
        int maxLength = 0;
        int right = 0;
        int left = 0;
        Set<String> set = new HashSet<String>();
        char[] chars = s.toCharArray();
        while (right<chars.length){
            String rightEle = String.valueOf(chars[right]);
            if(!set.contains(rightEle)){
                //集合中没有当前元素
                set.add(rightEle);
                //移动右指针
                right++;
            }else{
                String leftEle = String.valueOf(chars[left]);
                //集合中有当前元素 移动左指针
                set.remove(leftEle);
                left++;
            }
            length = set.size();
            if(maxLength<length){
                maxLength = length;
            }
        }
        return maxLength;
    }
}