48. 最长不含重复字符的子字符串

题目

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

示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

思路

• 哈希表：遍历字符串s，map的key为s.charAt(j),value为j
• 更新左指针：出现重复元素时更新i,i为上一次重复元素出现的索引，保证[i+1,j]内无重复字符且最大
• map加入值
• 更新结果res：取上轮res和本轮双指针区间[i+1,j]的宽度的最大值

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length()==0){
            return 0;
        }

        Map<Character,Integer> map=new HashMap<>();
        int res=0;
        //从-1开始j-i是[i,j]闭区间的个数例如3--1=4是索引0-3的个数
        int i=-1;

        for(int j=0;j<s.length();j++){
            if(map.containsKey(s.charAt(j))){
                i=Math.max(i,map.get(s.charAt(j)));
            }
            map.put(s.charAt(j),j);

            res=Math.max(res,j-i);
        }

        return res;
    }
}

复杂度

时间复杂度O(n): n为字符串的长度
空间复杂度O(1): 字符的ASCII码范围0-127哈希表map最多使用O(128)=O(1)的额外空间