最长无重复字串

记录下思路。
首先想到双指针，始终保证左右指针之间元素无重复。
1.为了判断重复，用 Map 保存区间内元素的（元素值，索引）。
2.若右指针行至某一元素发现其已在区间内存在，则记录此时区间长度并更新最长字串长度。
3.更新区间及区间内元素：Map中去除左指针至重复元素索引位置这一段的元素键值对；并把左指针指向该元素位置右一处。

    public int maxLength (int[] arr) {

        Map<Integer, Integer> map = new LinkedHashMap<>();
        int right = 0, left = 0, len = arr.length, max = 0;

        for(int tmp, cur; right < len; left = cur){

            for(tmp = right - left; right < len && !map.containsKey(arr[right]); tmp++, right++){
                map.put(arr[right], right);
            }
            max = tmp > max ? tmp : max;
            if(right >= len) return max;

            cur = map.get(arr[right]) + 1;
            for(int i = left; i < cur; i++){
                map.remove(arr[i]);
            }
        }
        return max;

    }

优化：
考虑到每次判重后都要在 Map 中删除一段元素，思考能否通过更新元素最近出现的位置以避免 Map 删除操作。
思路：
1.每次更新当前元素，保证 Map 中元素对应的位置为最近出现的位置；
2.若重复元素上次出现的位置在左指针左侧，则不视为重复；
3.遇到重复元素，则记录区间长度并更新最长字串及左指针位置。

public int maxLength (int[] arr) {

    Map<Integer, Integer> map = new HashMap<>();
    int right = 0, left = 0, max = 0;

    for(int tmp = 0, cur; right < arr.length; right++){

        cur = arr[right];
//      判重：包含元素位置在左指针左侧不视为重复
        if(map.containsKey(cur) && map.get(cur) >= left){
//          遇重则更新左指针并记录当前字符长度
            tmp = right - left;
            left = map.get(cur) + 1;
        }
//      每次更新当前元素最新位置
        map.put(cur, right);
        max = tmp > max ? tmp : max;
    }
    return max;

}