题目地址: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

题目要求:

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

示例 1:

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

示例 2:

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

示例 3:

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

代码

public class Solution {
    @Test
    public int lengthOfLongestSubstring(String s) {
        if(s==null || s.equals("")){  //判断传入字符串是否为空
            return  0;
        }

        int fast=0,slow=0;  //定义快慢指针
        int max=0;          //计算窗口大小  (fast-slow+1)

        char[] chars=s.toCharArray();//将字符串转化为字符数组方便操作
        HashMap<Character,Integer> appearChar=new HashMap<Character, Integer>();//记录出现过的字符和出现时的下标
        for(  ;fast<chars.length;fast++){   //快指针从头遍历到尾
            if(appearChar.containsKey(chars[fast])){    //如果出现过该字母
                slow=max(appearChar.get(chars[fast])+1,slow);    //slow慢指针为出现过该字母的下一位
                                                                //防止指针后退,不能低于当前位置
            }
            appearChar.put(chars[fast],fast);                   //每个遍历的字母都要存入
            max=max(max,fast-slow+1);                                    //计算快慢指针的窗口大小,因为要保留最大窗口大小，所以使用max函数保留最大窗口值

        }
        return max;         //返回窗口大小
    }
}

思路

要求只是求出无重复字母字符串长度,而不是内容
设置快慢指针 fast和slow 形成窗口大小
使用hashmap存放 <出现过的字母,下标>
fast和slow同时从0开始,fast每次步进为1
每次遇到出现过的字母,slow跳到"出现过的字母"下标的下一位
窗口大小也就是字符串大小=(fast-slow+1)

难点

防止slow指针后退, 例如: abba的情况slow指针会后退
窗口大小一直在变化,只要统计最大值就好

解决方法

1. 防止slow指针后退使用max(slow,appearChar.get(chars[fast])+1 )
2. 也是使用max函数 max=max(max,fast-slow+1);

学习视频

https://www.bilibili.com/video/BV1zk4y1C7c5?spm_id_from=333.337.search-card.all.click