题解 | 最长不含重复字符的子字符串

import java.util.*;


public class Solution {
    // 找到字符串中最长的不包含重复字符的子字符串，返回最长子字符串的长度
    // 思路：双指针遍历字符串，最后返回两个指针的差值就是最长字符串的长度
    // 关键词：最长，不含重复字符
    // 最长要靠双指针，重复字符要靠哈希表
  	// 在这段代码中，没有用到双指针，只用了一个指针回溯来遍历整个字符串，通过哈希表本身不含重复元素的性质，key为字符，value为该字符对应的index；当遇到重复的字符，就找到对应字符在当前记录的子字符串的位置，之后将该位置之前的所有字符remove。之后有一个关键点在于，当把重复位置（含重复位置）之前的字符remove后，之后的几个字符可能也已经添加到哈希表中了，我们需要通过改变right的值来将其定位到没有被遍历过的新字符的位置上，通过right = index + hashMap.size()实现。
    public int lengthOfLongestSubstring (String s) {
        if(s.length() == 1) return 1;
        // write code here
        // 指针需要回溯
        int right = 0;
        HashMap<Character,Integer> hashmap = new HashMap<>();
        // 每次比较max和当前遍历到的字符串的长度
        int max = Integer.MIN_VALUE;
        while(right < s.length()){
            if(!hashmap.containsKey(s.charAt(right))){
                // 这里记录每次加进来的字符的key和对应位置的value
                hashmap.put(s.charAt(right),right);
                max = Math.max(max,hashmap.size());
                right++;
            }else{
                // 遇到重复的字符，就找到对应字符在当前记录的子字符串的位置，之后将该位置之前的所有字符remove
                max = Math.max(max,hashmap.size());
                int index = hashmap.get(s.charAt(right));
                for(int i = index;i>=0;i--){
                    hashmap.remove(s.charAt(i));
                }
                right = index + 1 + hashmap.size();

            }
        }
        return max;
    }
}