【力扣 Hot100 | 第二天】4.11 无重复字符的最长子串

2.无重复字符的最长子串

2.1题目

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

• 示例一：

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

2.2解法一：滑动窗口

2.2.1解题思路

• 使用一个for循环代表窗口的结束位置，一个变量left代表窗口的起始位置；

• 使用一个map集合存储字符串中的 字符 以及在字符串中的索引位置 ；

• 每次循环中，若map集合没有该字符，则将该字符以及索引位置存放到map中；

• 若已经存在该字符，则需移动left起始位置， left在（原有的left，重复字符的下一个位置）两个中取最大值

  • 目的：确保left起始位置不会往前移动

  • 例子：

    #求字符串 abba 的无重复字符的最长子串
    
    #在遍历索引为3的字符a时，left值为2
    #left在（原有的left：2，以及重复字符a索引的下一个位置，即1）中应该取原有的2
    #若left取了1，则left往前移动了
    

• 原有的max长度和 （ j-left+1 ）比较，取最大值

2.2.2代码实现

	public int lengthOfLongestSubstring(String s) {
        
        if(s.length()==0){
            return 0;
        }
        
        Map<Character,Integer> map=new HashMap<>();
        int max=Integer.MIN_VALUE;
        int left=0;
        for(int j=0;j<s.length();j++){
            char ch=s.charAt(j);
            if(map.containsKey(ch)){
                left=Math.max( left, map.get(ch)+1);  //起始位置取原来的值 或者 重复字符的下一位
            }
            //加入该字母
            map.put(ch,j);
            max=max>j-left+1?max:j-left+1;			//更新最长子串的长度
        }
        return max;
    }