https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

我的答案

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int left = 0, right = 0;
        int res = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            if (!map.containsKey(c) || map.get(c) < left) {
                res = Math.max(right - left + 1, res);
            } else {
                left = map.get(c) + 1;
            }
            map.put(c, right);
            right++;
        }
        return res;
    }
}

双指针+哈希表方法，要注意一点map.get(c) < left，这个条件，当left指针向前跳跃时map中被跳过的key就失效了，不用真正删除map中的key，如果小于left说明失效。

最优解

    public int lengthOfLongestSubstring(String s) {
        int[] cache = new int[128];
        for (int i = 0; i < 128; i++) {
            cache[i] = -1;
        }
        int n = s.length();
        int res = 0;
        int left = 0;
        for (int i = 0; i < n; i++) {
            int index = s.charAt(i);
            if (cache[index] >= left) {
                left = cache[index] + 1;
            }
            res = Math.max(res, i - left + 1);
            cache[index] = i;
        }
        return res;
    }

用数组代替了map，作用是相同的，是提升速度的关键。另外，计算过程也更精简，关键是计算左边界。如果cache[index] >= left，说明子串中包含重复元素，需要跳跃。