剑指Offer48.最长不含重复字符的子字符串

题目：https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/

思路：滑动窗口。用map记录每个字符出现的位置。当字符不在map中时，就往map中添加字符和位置，当字符在map中时，考虑map中记录该字符的位置i是不是比窗口的左端小，若是，则不影响当前窗口；否则，要将窗口左端移动至i+1的位置，这样才能保证窗口内部没有重复字符串。

代码：

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

 优化：用数字实现哈希表的操作

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] map = new int[128];  //长度为128的数组存放字符下表
        for(int i=0; i<128; i++) map[i] = -1;
        int left, right, len;
        left = right = len = 0;
        while(right < s.length()){
            int c = (int)(s.charAt(right));
            if(map[c] >= 0 && map[c] >= left){
                left = map[c] + 1;
            }
            len = Math.max(len, right - left + 1);
            map[c] = right;
            right++;
        }
        return len;
    }
}

执行用时：2 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：38.8 MB, 在所有 Java 提交中击败了58.61%的用户