（每日一题）——最长不含重复字符的子字符串

• • 剑指 Offer 48. 最长不含重复字符的子字符串

难度中等460

题目：请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:

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

示例 2:

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

示例 3:

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

提示：

• s.length <= 40000

思路

这道题说实话，看上去很难，刚开始想弄两个for 循环，但是复杂度太高了，在想能不能一次遍历解决这个问题

后面看到了滑动窗口，滑动窗口有一个右边界和左边界，随着定义的条件动态的改变左边界和右边界的值

首先左边界刚开始没有，只有遇到相同元素才出现左边界，右边界就是遍历元素的下标，一直在移动，

只要重复元素出现就缩短左右边界距离

题目算法代码如下

public class 最长不含重复字符的子字符串 {
    
    public int lengthOfLongestSubstring(String s) {
    
        Map<Character, Integer> map= new HashMap<>();
        //结果
        int result=0;
        //刚开始的左边界还不存在，遇到相同元素才出现左边界
        int left=-1;
        //右边界为0
        for (int j= 0;j<s.length() ; j++) {
    
            if (map.containsKey(s.charAt(j))){
    
                  //缩短左边界 ，因为是取最大值，下标往右指针靠，就是短了
                  left=Math.max(left,map.get(s.charAt(j)));
            }
            //没有重复，右边界可以不断滑动
            map.put(s.charAt(j),j);

            //更新滑动窗口大小
            result=Math.max(result,j-left);
        }
        return result;
    }

}