[LeetCode 3] 无重复字符的最长子串

🎯 请点击上方原题链接，查看题目描述👆

💭 解题思路#

定义一个“窗口”，“窗口”的左边界 left = 0 ,右边界 right = 0
定义一个 Map 字典，字典里的 key 记录着窗口增大时途径的节点。 value 为节点 key 的下标值，每次窗口右边界增大 right++ ，就检查右边界下标 right 对应的字符在不在“字典”:

如果不在字典，说明窗口内的字符都是符合要求的，接着扩大窗口
如果在字典里的话，就需要计算一下窗口大小，并且根据情况缩小左边窗口
- 如果下标 right 对应的字符在窗口，需要把左边界 left 定位到重复字符的下一个字符
- 如果下标 right 对应的字符不在窗口内，就不用管

理解左窗口缩小的时机是需要我们解题的关键！

假设当前窗口右边界 right 对应的字符为 A，上一次字符A出现的下标为 index 。 left < index < right 是不是就说明了出现重复字符了，只有这时候才需要缩小窗口

💻 代码实现#

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> window = new HashMap<>();
        int left = 0,right = 0,res = 0;
        while(right < s.length()){
            char temp = s.charAt(right);
            if(window.containsKey(temp)){
                res = Math.max(res,(right - left));

                //这里是关键，很多人都写成了 left = window.get(temp) + 1;
                left = Math.max(left,window.get(temp) + 1);
            }
            window.put(temp,right);
            right++;
        }
        res = Math.max(res,(right - left));
        return res;
    }
}