8.8 剑指刷过，隔了几周又刷不出来了
8.9 不能一次 AC
8.10 可以 AC

第一次复习
9.6 无法 AC
9.7 可以 AC
9.14 可以 AC

题目描述

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

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

解题思路：动态规划

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

• 怎么说呢，重点就是判断之前每一个状态的长度与当前的字符索引减去以当前字符为基的在 map 集合中已经存在的索引或不存在的索引(不存在则是 -1 )的距离，前者如果小于后者，说明还没有遇到重复的字符，可以继续追加字符，增加长度！

• 差不多就这个意思！真尼玛难呢！

8.9 感悟：

下面第 9 行代码：这里返回 -1 是个技术活，如果有重复字符出现的话，当前下标与 rep 相减就能得出长度；而如果没有重复元素的话，当前下标与 rep (-1) 相减得到得结果就会反而 +1 ,它的作用是：判断之前状态的无重复最长字串的长度时肯定会比用当前索引减去值为 -1 的 rep 的状态长度小，因为后者减去的是负数，值肯定比之前状态的长度要更大，所以当前的状态就可以继续 +1！

所以得出个结论：不止是 -1，负多少都可以，只要是个负数就行。

9.6 心得：

• 大体代码自己拼命想，可以敲出来，最后最关键的一步就是下面第 19 行的 i - rep > tmp，肯定要大于 tmp 呀！！！！不是重复的元素从 map 取出来就是 -1，i - (-1) 肯定大于之前的长度 tmp；

• 换句话说，之前的 tmp 就是拿来让我们衡量是否可以进一步使无重复字符的最长字串长度 +1 的！

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 存字符与该字符的索引
        Map<Character, Integer> map = new HashMap<>();
        // res 为结果
        // tmp 为每一个状态 dp,表示以字符 s.charAt[i] 结尾的 “最长不重复子字符串” 的长度。
        int res = 0, tmp = 0;
        for(int i = 0; i < s.length(); i++) {
            int rep = map.getOrDefault(s.charAt(i), -1); // 获取重复元素的索引 rep，如果没有则返回 -1 
            map.put(s.charAt(i), i); // 更新哈希表; 一定要在上面获取了之后再存
            // i - rep > tmp 表明 map 集合之前没有存相同的值，所以 rep = -1
            // 既然 rep = -1, 那 i - rep 肯定大于之前 tmp 的长度;
            // 也就变相的表明无重复字符的最长子串可以继续增长，级 tmp + 1
            tmp = i - rep > tmp ? tmp + 1 : i - rep; 
            res = Math.max(res, tmp); 
        }
        return res;
    }
}