leetcode热题系列之无重复字符的最长字串（003）

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

题目和示例：

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

示例 1:

输入: “abcabcbb”

输出: 3

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

示例 2:

输入: “bbbbb”

输出: 1

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

示例 3:

输入: “pwwkew”

输出: 3

解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。

请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

思路：

1. 首先只要有关于重复的字眼，都要思考是否能用上HashMap这个数据结构。

具体来说，这个是存在字符的下一个位置（很好理解，既然 ‘我’ 都重复了 当然要从下一个位置开始）

3. 这里用到了TCP的滑动窗口的思想。

具体做法：

1. 首先定义窗口的左右指针 left right

2. right一步一步往右边走

3. 每当遇到一个字符我们就要判断这个字符是不是在hashmap当中

4. 若是 重新判断起点：究竟是维持原起点还是更新Hashmap的值？

比如：abba 当left在第二个b right走到a的时候 left当然不会返回第一个b。

所以我们只需要在这里加一个Math.max()即可。

5. 边走的同时也要更新ans的结果。

代码：

package Hot003;

import java.util.HashMap;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int length = s.length();
        int ans = 0;
        HashMap<Character,Integer> hashMap = new HashMap<>();
        
        for(int left = 0,right = 0; right<length;right++){
            char temp = s.charAt(right);
            if(hashMap.containsKey(temp)){ //重复
                left = Math.max(hashMap.get(temp),left);
            }
            ans = Math.max(ans,right-left+1);
            hashMap.put(temp,right+1);
        }
        return ans;
    }
}
           

github地址：

https://github.com/CLFlemon/LeetcodeHot100