九章算法面试高频题冲刺班2021

最长不含重复字符的子字符串（剑指offer48题）

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

示例 1:

输入: "abcabcbb"

输出: 3

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

双指针+哈希表 时间复杂度O(N) 空间复杂度O(1):字符的 ASCII 码范围为 0 ~ 127 ， 哈希表 dicdic 最多使用 O(128) = O(1)大小的额外空间。class Solution {    public int lengthOfLongestSubstring(String s) {        Map<Character, Integer> dic = new HashMap<>();        int i = -1, res = 0;        for(int j = 0; j < s.length(); j++) {            if(dic.containsKey(s.charAt(j)))                i = Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i            dic.put(s.charAt(j), j); // 哈希表记录            res = Math.max(res, j - i); // 更新结果        }        return res;    } }