无重复字符的最长字串

链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

解题思路：滑动窗口

大家看到滑动窗口这种类型题不要怕，本质上它就是双指针。

初始化：

• 初始化变量 Map<Character,Integer> map = new HashMap<>()，map 的 key 存储遍历的字符，value 存储当前遍历字符在字符串中的索引
• 初始化变量 int max，表示最长的无重复子串的长度，作为返回值
• 初始化变量 int left，作为滑动窗口的左指针
• 变量 int i，作为遍历指针，同时它也是滑动窗口的右指针

算法思路：

• 滑动窗口维护最长的无重复子串
• 遍历字符串的过程中，如果 map 已经包含当前字符 char[i]，则说明我们需要重新维护当前的滑动窗口，让左指针left 更新为 left 与 map.get(chars[i]) + 1)中较大的那一个
• 将当前的字符和字符索引更新到 map 中
• 更新 max

流程模拟：

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();
        Map<Character,Integer> map = new HashMap<>();
        int left = 0;
        int max = 0;
        for(int i = 0; i < chars.length; i++){
            if(map.containsKey(chars[i])){
                left = Math.max(left,map.get(chars[i]) + 1);
            }
            map.put(chars[i],i);
            max = Math.max(max,i - left + 1);
        }
        return max;
    }
}

复杂度分析

• 时间复杂度：

N 为字符串的长度，我们只需要从头至尾遍历一次字符串就可以得到目标解，所以时间复杂度为

• 空间复杂度：

我们申请了一个哈希表，哈希表中需要存储字符串中所有不相同的字符个数，记作 M，所以额外空间复杂度为