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

一、题目

给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。

示例一：

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例二：

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例三：

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

示例四：

输入: s = “”
输出: 0

提示：

• 0 <= s.length <= 5 * 10^4
• s由英文字母、数字、符号和空格组成

二、相关链接

• 题目链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
• 参考题解：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-jie-suan-fa-3-wu-zhong-fu-zi-fu-de-zui-chang-z/

三、解题思路

• 解法：哈希表+移动窗口
• 思路：从左到右用end遍历字符串并存起来(字符+下标)，遇到重复的字符的话就重置start，并计算长度length=end-start+1

四、代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        //用哈希表基表每个字符的下标，然后遇到有重复的就去掉上一个重复的的
        //如abca去掉上一个重复的a就是bca就是无重复字符的子串

        Map<Character, Integer> map = new HashMap<>();
        int result = 0;

        int start = 0;
        for(int end=0;end<s.length();end++){
            char c = s.charAt(end);
            if(map.containsKey(c)){
                // start = map.get(c) + 1;
                // 需要加这个字段防止定位到不连续的下标去(比如abba)
                start = Math.max(map.get(c)+1, start);
            }

            result = Math.max(result, end-start+1);
            map.put(c,end);
        }

        return result;
    }
}

五、总结

• 难度：中等
• 总结：移动窗口题型没做过，需要多做，做熟悉

六、测试用例不通过记录

1.没有对特殊情况做判断(边界)

失败用例：”abba”
错误结果: 3
预期结果: 2
修改前：start = map.get(c) + 1;
修改后：start = Math.max(map.get(c)+1, start);
解释：

• 遍历完第三个字符b的时候，start=2,end=2
• 遍历到第四个字符a的时候，start=map.get(3)+1=1，但是此时start=end=2（并没有包含了下标为0的a），所以我们不能执行start=1
• start = Math.max(map.get(c)+1, start);执行这个的理由是判断map.get(c)是否包含在start->end中
  • 包含：start = map.get(c) + 1
  • 不包含（不处理）：start = start