8.无重复字符的最长字串

参考链接

3. 无重复字符的最长子串 - 力扣（LeetCode）

3. 无重复字符的最长子串 - 力扣（LeetCode）- Krahets 题解

个人尝试

一路磕磕碰碰的尝试总算是做出来了...

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;
        if (s.length() == 1) return 1;
        // 存储出现过的字符+索引
        Map<Character, Integer> map = new HashMap<>();
        char[] cArr = s.toCharArray();
        int res = 0;
        // 滑动窗口
        for (int i = 0, j = 0; i < cArr.length && j < cArr.length; j++){
            Integer tmp = map.get(cArr[j]);
            if (tmp == null || tmp < i) {
                // 字符第一次出现
                res = Math.max(res, j - i + 1);
                map.put(cArr[j], j);
            } else {
                // 字符重复出现
                i = tmp + 1;
                map.put(cArr[j], j);
            }
        }
        return res;
    }
}

// 可缩减代码优化成：
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;
        if (s.length() == 1) return 1;
        // 存储出现过的字符+索引
        Map<Character, Integer> map = new HashMap<>();
        char[] cArr = s.toCharArray();
        int res = 0;
        // 滑动窗口
        for (int i = -1, j = 0; i < cArr.length && j < cArr.length; j++){
            Integer tmp = map.get(cArr[j]);
            if (tmp == null || tmp < i) {
                // 字符不在滑动窗口范围内重复出现
                res = Math.max(res, j - i);
            } else {
                // 字符在滑动窗口内重复出现
                i = tmp;
            }
            map.put(cArr[j], j);
        }
        return res;
    }
}

优秀题解

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int i = -1, res = 0, len = s.length();
        for(int j = 0; j < len; j++) {
            if (dic.containsKey(s.charAt(j)))
                i = Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i
            dic.put(s.charAt(j), j); // 哈希表记录
            res = Math.max(res, j - i); // 更新结果
        }
        return res;
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。