【Day34】LeetCode算法 -- 3. 无重复字符的最长子串

.29.

发布于 2022-11-15 14:00:10

1770

发布于 2022-11-15 14:00:10

文章被收录于专栏：个人技术博客

刷题打卡，第 34 天

题目一、3. 无重复字符的最长子串

题目一、3. 无重复字符的最长子串

原题链接：3. 无重复字符的最长子串

题目描述：

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。 / 示例 1: 输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。 / 示例 2: 输入: s = “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。 / 示例 3: 输入: s = “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。请注意，你的答案必须是子串的长度，“pwke” 是一个子序列，不是子串。 / 提示：

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

解题思路：题目会给定一个字符串s，我们需要返回其中最长子串的长度，注意，这里返回的是最长子串长度而非最长子序列长度。例如：“abbcde”,最长子串是“bcde” ；最长子序列是“abcde” ；

我们可以模拟出一个窗口来扫描字符串的每一个字符，窗口有左边界和右边界，我么用下标left = 0和下标right = 0来对应左右边界，在接下来的扫描中，我们会遇到两种情况：

扫描到的字符不存在于窗口中，那么我们的右边界right + 1后移,将元素包含进窗口中，记录下当前窗口的最大长度，对应着当前不重复子串的最大长度，然后继续扫描剩下的字符。
扫描到的字符在窗口中存在，那么这时候我们就需要将左边界 left + 1后移，缩短窗口，重复这样的操作直到当前扫描的元素不存在于窗口中。

循环进行上述操作，当我们窗口的有边界抵达字符串s的尾部，也就是扫描完整个字符串后，返回记录下来的当前最大子串长度即可。

为了判断扫描到的元素是否存在于窗口中，我们会使用到内容不可重复的集合Set，用Set集合充当窗口，将扫描到的字符用Set集合来保存，能成功保存就说明当前元素不存在于窗口中，不能添加就说明当前元素存在于窗口中。

提交代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0) return 0; //若字符串为空或长度为0，直接返回0

        Set<Character> set = new HashSet<>();      //创建不可重复的Set集合，充当扫描的窗口
        int left = 0,right = 0,max = 0;    //左边界下标left，右边界下标right，最长不重复子串长max
        int length = s.length();           //获取字符串的长度

        while(right < length){             //在字符串被扫描完之前
            char r = s.charAt(right);      //扫描right下标位置的值
            if(set.add(r)){                //如果成功加入Set集合
                max = Math.max(max,right-left+1);//记录当前最长不重复子串的长度
                ++right;                         //向后扫描
            }else{                         //如果无法加入Set集合
                char l = s.charAt(left);   
                set.remove(l);             //left下标后移，缩减窗口长度
                ++left;                    
            }
            
        }
        return max;  //返回记录下的窗口历史最长大小，即：最长子串的长度。
    }
}

提交结果：