无重复字符的最长子串

原题链接

• 经典的滑动窗口问题。

使用的方法

• Map.containsKey(): 判断 Map 中是否包含指定的键。

解题思路

• 使用滑动窗口和哈希表来记录当前窗口内的字符及其索引。
• 初始化两个指针 start 和 end，分别表示当前窗口的起始和结束位置。
• 遍历字符串，当遇到一个字符时，检查它是否已经在哈希表中出现过。
• 如果该字符已经存在于哈希表中，说明当前窗口内有重复字符，需要将 start 指针移动到上一个出现该字符的位置的下一个位置，以确保窗口内没有重复字符。
• 更新哈希表中该字符的索引为当前 end 的位置。
• 在每次更新窗口时，计算当前窗口的长度，并更新最大长度 ans。

代码实现

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