题目:

3. 无重复字符的最长子串

解法:

思想, 使用滑动窗口, 下标 i 表示左边界, 下标 j 表示右边界. i 和 j 之间的长度是不重复的子串的长度.

j 一步一步的走, 用一个HashMap存储j走过的元素(元素 --> 下标).
对于i来说, 只有当出现重复元素的时候才需要更新. 当重复的时候, 取重复位置的最大下标+1. 但是我们不删除过往的元素, 也就是说过期的元素依然会存在于HashMap中, 这时候我们就直接取 (重复元素的下标+1) 和 当前位置的最大值.
然后每轮结束的时候计算一次长度, 和之前的相比取最大.

流程为:
==> j 往右边走;
==> 遇到重复元素, i 需要是否需要更新, 取决于重复元素是否过期(也就是重复的元素的下标比 i 的小, 就不更新 i ) ;
把 j 位置的元素压入HashMap;
计算长度, 和历史相比取最长;
直到结束.

public int lengthOfLongestSubstring(String s) {
    // 滑动窗口, 用 HashMap判断重复
    Map<Character, Integer> map = new HashMap<>();
    int res = 0;
    for (int i = 0, j = 0; j < s.length(); j++) {
        // 当前j位置的字符
        char ch = s.charAt(j);
        if (map.containsKey(ch)) {
            i = Math.max(map.get(ch) + 1, i);
        }
        map.put(ch, j);
        res = Math.max(res, j - i + 1);
    }
    return res;
}

可以使用数组优化Hashmap

public int lengthOfLongestSubstring(String s) {
    // 使用数组优化HashMap, 把数组看作是特殊的Hashmap
    int[] map = new int[128];
    int res = 0;
    for (int i = 0, j = 0; j < s.length(); j++) {
        char ch = s.charAt(j);
        // 每次都取最大的i, 因为index比i小的元素被认为是过期的, 无效的
        i = Math.max(map[ch], i);
        // 每次都put
        map[ch] = j + 1;
        // 计算总长
        res = Math.max(res, j - i + 1);
    }
    return res;
}