LeeCode——3. 无重复字符的最长子串

题目

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

示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

思路

一开始想的是直接暴力求解，挨个循环过去，然后判断子串是否为符合要求的。

for(int i = 0; i < s.length(); i++)
	for(int j = 0; j < s.length(); j++)
		if(子串(i-j)无重复字符)
			max = 子串.length()

时间复杂度在O(n^3)，超时，所以要去想如何优化。
首先，每次都判断一整个子串是否为不重复子串肯定不可行，每次判断都需要花费一定的时间复杂度，我们可以把子串当成一个滑块，滑块起点为left，滑块终点为right，每次扩展滑块时，判断在滑块区间内是否已有新元素，若已有，滑块左侧缩短,left++，若没有，则扩展滑块，将新元素加入滑块右侧，right++。滑块可以用队列来维护。
代码如下：

class Solution {
    //维护一个队列，如果重复了，头出队，不重复，新元素入队
    public int lengthOfLongestSubstring(String s) {
        if(s.length() == 0){
            return 0;
        }
        int max = 0;
        LinkedList<Integer> list = new LinkedList<Integer>();
        
        int left = 0,right = 0;
        int len = s.length();
        
        while(left < len && right < len){
            //不包含，添加
            if(!list.contains((int)(s.charAt(right)))){
                list.add((int)(s.charAt(right)));
                right++;
                if(right - left > max){
                    max = right - left;
                }
            }else{
                //删除头部元素
                list.remove();
                left++;
            }
        }
        
        return max;
    }
}

如有错误，还望指出，谢谢观看。