LeetCode百题【无重复字符的最长子串】

题目描述

思路

• 滑动窗口

class Solution {
    /**
     * 滑动窗口
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        int res = 0;//返回结果
        int left = 0;//左指针，右指针用i代替
        Map<Character, Integer> map = new HashMap<>();//定义映射关系，字符->出现最后位置的下标
        for (int i = 0; i < s.length(); i++) {
            char temp = s.charAt(i);

            //1.如果出现了重复字符，移动左指针,使滑动窗口内部的字符不重复
            if (map.containsKey(temp)) {
                //比较大小是为了防止指针左移的情况如 "abba"
                left = Math.max(left, map.get(temp) + 1);
            }
            //没有就放进散列表，有就更新下标的最大值
            map.put(temp, i);
            //维护更新不重复子串的最大值
            res = Math.max(res, i + 1 - left);
        }
        return res;
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters