【leetcode】题解 3. 无重复字符的最长子串

题目描述 力扣https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

class Solution {
    public int lengthOfLongestSubstring(String s) {
         Set set = new HashSet();
        int length = 0;
        int right = 0;
        for (int i = 0; i < s.length(); i++) {
            if (i > 0) {
                set.remove(s.charAt(i - 1));
            }
           
            while (right < s.length() && !set.contains(s.charAt(right))) {
                set.add(s.charAt(right));
                ++right;
            }
            length = Math.max(right - i , length);
        }
        return length;
    }
}

 这道题我以前刷过一次，这个解答和官方思路类似，滑动窗口，但是这个解答有一点问题，每次循环的时候，起点未必是上一次起点+1，即未必是第一位重复导致结束的上一次循环，因此中间可以省略掉一部分循环，这里贴了一下别人的解答

public int lengthOfLongestSubstring(String s) {
        HashMap map = new HashMap<>();
        int max = 0, start = 0;
        for (int end = 0; end < s.length(); end++) {
            char ch = s.charAt(end);
            if (map.containsKey(ch)){
                start = Math.max(map.get(ch)+1,start);
            }
            max = Math.max(max,end - start + 1);
            map.put(ch,end);
        }
        return max;
    }

用map记录了字符的索引，下一次的起始字符坐标取最新的坐标，这样避免了无效循环