目录

錄题目

聾思路解析

代码实现

复杂度分析

题目链接：无重复字符的最长字串

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

示例1：

输入：s = abcabcbb
输出：3
解释：abc，bca，bc，b，最长的无重复字符子串的长度为3

示例2：

输入：s = bbbb
输出：1
解释：b为最长的无重复字串子串，长度为1

示例3：

输入：s = pwwkew
输出：3
解释：pw，w，wke，最长无重复字符子串的长度为3

聾思路解析

我们这里以abcabcbb为例

从上图中可以发现起始位置递增，结束位置也是递增，于是可以用滑动窗口的思路来解决这个问题，具体做法如下：

1. 我们使用左右两个指针，左指针标记子串起始位置，右指针标记字串结束位置
2. 左指针往右走的时候，我们发现子串会将前一个字符删除
3. 右指针则继续从上一个字串结束的位置往右走
4. 右指针往右遍历的规则是，后续字符在当前字串中不存在，并且右指针往右走的时候不能越界
5. 当右指针满足条件时，将右指针每次遍历的字符都存在HashSet中，因为HashSet方便我们判断子串中是否有将要添加的字符
6. 在左指针每次往右走之前将新的子串与上一个子串的长度进行比较，记录最大值 

代码实现

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set m = new HashSet<>();
        //窗口问题
        //如果右边界开始给0，则[left,right),如果边界给-1，则[left,right]
        //这个会影响最后长度的比较  子串长度right-i         字串长度right-i+1
        int right = -1;   //字符串的右边界,刚开始最长字符串中没有字符，故边界给-1
        int size = s.length();   
        int count = 0;   //无重复字符串的长度字符串
        for(int i = 0;i < size;i++){  //i为左边界，依次朝右走
            if(i != 0){
                m.remove(s.charAt(i-1));  //每次左边界右移的时候，需要将前一个字符删除
            }
            //右边界不能越界，且s的下一个字符不在当前子串中
            while(right+1 < size && !m.contains(s.charAt(right+1))){ 
                m.add(s.charAt(right+1));  //向哈希set中添加
                right++;
            }
            count = Math.max(count,right-i+1); //更新长度
        }
        return count;
    }
}

复杂度分析

时间复杂度：左右指针分别遍历了一次字符串，故时间复杂度为O(2N),也就是O(N)

壟空间复杂度：我们借助了HashSet这一数据结构，里面存储着无重复字符的字符，存储的长度最大为128，因为ASCLL码的范围为[0,128),故空间复杂度为O(M)，M为字符的个数，M最大为128