3. 无重复字符的最长子串【539】== 剑指 Offer 48. 最长不含重复字符的子字符串【15】

小咪咪 2023-09-27 12:04 96阅读 0赞

> **难度等级：中等**

> **上一篇算法：**
> 
> [剑指 Offer 38. 字符串的排列【字符串】][Offer 38.]

> **力扣此题地址：**
> 
> [剑指 Offer 48. 最长不含重复字符的子字符串 - 力扣（Leetcode）][Offer 48. _ - _Leetcode]

### 1.题目：最长不含重复字符的子字符串 ###

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。假设字符串中值包含‘a’-‘z’的字符。例如，在字符串“arabcacfr”中，最长的不含重复字符的子字符串是“acfr”，长度为4。

![320a259322de40c6962e4a7fad00951b.png][]

### 2.解题思路 ###

> 滑动窗口（双指针）+HashMap记录重复字符位置
> 
> 左右指针，左指针指向重复元素，右指针从左向右遍历，用HashMap判断元素是否为重复元素。
> 
> ![dae4f7b271344af4870da60034415cb4.png][]

### 3.代码实现 ###

class Solution {
        public int lengthOfLongestSubstring(String s) {
            /*
            滑动窗口(双指针)+HashMap记录s[i]出现过的最近位置:
            每读取一个s[i],判断一下map中是否出现过s[i]
            若出现过,说明s[i]要加入窗口,左指针必须向右收缩才能使得窗口内的字符不重复
            如(dabc)abc当遍历s[3]=a时,左边的a必须出去da(bca)bc
            细节&坑点:left指针回退现象
            left指针必须满足两个条件:left指针向右收缩&&将上一个出现过的s[i]逐出窗口
            eg:ab(bc)adf->a(bbca)df指针回退现象
            因此为了避免left指针回退情况出现,left指针维护时要满足上面两个条件:
            1.不能比上次的left小;2.位于上一个出现过的s[i]位置后(两者取大的)
            */
            // 阴间案例
            if(s == null || s.length() == 0) {
                return 0;
            }
            int len = s.length();
            // 这里left初始化为-1是因为left(不含)右边才是窗口元素
            // 如(abc)abc,这里的right=0,1,2时left都不更新,left=-1
            // 计算出来的子串分别为1,2,3符合题意
            int left = -1;
            // 记录结果
            int res = 0;
            // 记录s[i]出现过的最近位置索引
            Map<Character, Integer> map = new HashMap<>();
            // 遍历右指针
            for(int right = 0; right < len; right++) {
                // 记录字符s[i]
                char ch = s.charAt(right);
                // 若map中出现过s[i],说明要更新一下left指针
                if(map.containsKey(ch)) {
                    // 为了避免指针回退,取大的
                    left = Math.max(left, map.get(ch));
                }
                // 更新结果
                // 注意这里的子串是right-left就可以
                // 因为我们维护的left是窗口左边缘,s[left]不是子串范围
                // 如ab(cab)c,遍历第二个b时会将left定位为1,也就是上一个b的位置
                // 结果就是4-1=3=子串长度
                res = Math.max(res, right - left);
                // 将s[i]加入map,维护s[i]出现的最大索引
                map.put(ch, right);
            }
            return res;
        }
    }

**无注解版:**

class Solution {
        public int lengthOfLongestSubstring(String s) {
            if(s == null || s.length() == 0) {
                return 0;
            }
            int len = s.length();
            
            int left = -1;
           
            int res = 0;
            
            Map<Character, Integer> map = new HashMap<>();
            
            for(int right = 0; right < len; right++) {
               
                char ch = s.charAt(right);
                
                if(map.containsKey(ch)) {
                    
                    left = Math.max(left, map.get(ch));
                }
                
                res = Math.max(res, right - left);
                
                map.put(ch, right);
            }
            return res;
        }
    }

[Offer 38.]: https://blog.csdn.net/m0_51697147/article/details/127387141
[Offer 48. _ - _Leetcode]: https://leetcode.cn/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/description/
[320a259322de40c6962e4a7fad00951b.png]: https://img-blog.csdnimg.cn/320a259322de40c6962e4a7fad00951b.png
[dae4f7b271344af4870da60034415cb4.png]: https://img-blog.csdnimg.cn/dae4f7b271344af4870da60034415cb4.png