[数据结构与算法]【leetcode】3. 无重复字符的最长子串

题目描述

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

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

题解

滑动窗口。
1、利用map记录每一个元素上一次出现的下标
2、固定left，移动right，当窗口中无重复的元素（map中不包含right的元素）right++
3、当right指向的元素已经在map中出现的时候，移动left：

left = Math.max(left, map.get(s.charAt(right)) + 1);
//map.get(s.charAt(right)) + 1 是right上一次出现的位置的 后一个位置。
//但是right上一次出现的位置，可能小于当前的left，比如abcba这个字符串，当left = 2，right = 3的时候。
//right + 1 = 4。此时应该检查a是否出现过。a出现过，移动left，但是a上一次出现在left之前，所以可以不用移动

4、每次移动滑动窗口之后，判断right - left + 1 和 res的大小，更新res。

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