2022-04-13 「3. 无重复字符的最长子串」

今日中等题：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

这题其实上周就做到了，但是因为思路不对，测试用例通过率卡在879 / 987上过不去。

最初思路比较简单，就是用HashMap去存一个已经出现过的字符，也不关心value是多少，只要有已经存过的，就把这个时候的尾取出来，和头相减，获得差值+1就是长度。
再把长度和最大值做比较，取最大即可，使用的是Math.max()方法。

但是开始想到的就是头和尾分别通过for循环遍历，导致双重for循环，时间复杂度高。

参考题解后发现，其实头可以固定不动，只遍历尾即可，如果遇到了重复字符，记录下当下长度后，把头换成重复字符中，位数更大的那一位即可。

看下代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;
        int ans = 0;
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        int head = 0;
        for (int i=0;i<s.length();i++) {
            if (map.containsKey(s.charAt(i))) {
                // 把头换成重复字符中，位数更大的一位
                head = Math.max(map.get(s.charAt(i)), head);
            }
            ans = Math.max(ans, i-head +1);
            map.put(s.charAt(i), i+1);
        }
        return ans;
    }
}