【leetcode】第3题：无重复字符的最长子串

曾经终败给现在 2022-02-21 07:41 152阅读 0赞

原文链接：[https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/][https_leetcode-cn.com_problems_longest-substring-without-repeating-characters]

说明：部分文字解析来自于原文。

### **目  录：** ###

**一、暴力解法【时间复杂度O(n^3)】**

**二、滑动窗口【时间复杂度为O(n)】**

**三、优化的滑动窗口**

--------------------

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

> **示例 1:**
> 
>     输入: "abcabcbb"
>     输出: 3 
>     解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
> 
> **示例 2:**
> 
>     输入: "bbbbb"
>     输出: 1
>     解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
> 
> **示例 3:**
> 
>     输入: "pwwkew"
>     输出: 3
>     解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
>          请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。

## 一、暴力解法【时间复杂度O(n^3)】 ##

*  虽然暴力解法不一定通过笔试，但是却是我这种菜鸟最容易写出来的，所以暴力解法的思路还是很重要的。先把题解出来，再讲究优化。可能题练习多了，对于非暴力解法才能很顺畅的写出来吧。

> 思路：和leetcode第五题：[求最长回文子串][Link 1] 的思路很像，都是遍历字符串的所有子串，找出长度最大的那个无重复字符的子串。为了减少遍历的次数，可以从长度最长的字符串开始遍历，这样只要找到不包含重复字符的子串，就可以停止遍历了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70][]

public class LengthOfLongestSubstring_3 {
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            String str = sc.next();
            getLengthOfLongestSubstring2(str);
        }
    
        public static int getLengthOfLongestSubstring2(String str) {
            if (str == null && str.length() < 1) {
                return 0;
            }
    
            int len = str.length();
            int maxSubLen = 0;
            int i = 0;
            int j = 0;
            boolean flag = false;
            for (i = len; i > 0; i--) {
                // 每次从所在位置最大的子串开始遍历
                // 长度为 i 的字符在整个字符串中的个数= len - i
                for (j = 0; j <= len - i; j++) {
                    if (allUnique2(str, j, i + j)) {
                        maxSubLen = i;
                        flag = true;
                        break;
                    }
                }
                if(flag){
                    break;
                }
            }
    
            System.out.println(maxSubLen);
            return maxSubLen;
        }
    
        public static boolean allUnique2(String str, int start, int end){
            Set<Character> set = new HashSet<>();
            String subStr = str.substring(start, end);
            for(int k = 0; k < subStr.length(); k++){
                if(set.contains(subStr.charAt(k))){
                    return false;
                }
                set.add(subStr.charAt(k));
            }
            return true;
        }
    }

*  **leetcode 代码实现：看着清爽一点，但是遍历次数要比上面的方法多一些，下面的代码需要遍历完所有的子串，而上面的方法从最大的子串开始遍历，找到不包含重复字符的子串就返回，所以遍历次数少一点。但是时间复杂度都是一样的：O(n^3)，是通不过笔试的。**

public class LengthOfLongestSubstring_3 {
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            String str = sc.next();
            getLengthOfLongestSubstring2(str);
        }
    
        // 暴力解法：判断所有的子串是否是无重复字符的子串，从最长的开始
        public static int getLengthOfLongestSubstring1(String str){
            if(str == null && str.length() < 1){
                return 0;
            }
    
            int len = str.length();
            int maxSubLen = 0;
            for(int i = 0; i < len; i++){
                for(int j = i + 1; j <= len; j++){
                    if(allUnique(str, i, j)){
                        // j是做完++后再去判断有无重复字符的，所以长度应该是：j - i
                        maxSubLen = Math.max(maxSubLen, j - i);
                    }
                }
            }
            System.out.println(maxSubLen);
            return maxSubLen;
        }
    
        public static boolean allUnique(String str, int start, int end){
            Set<Character> set = new HashSet<>();
            for(int i = start; i < end; i++){
                Character ch = str.charAt(i);
                if(set.contains(ch)){
                    return false;
                }
                set.add(ch);
            }
            return true;
        }
    }

--------------------

## 二、滑动窗口【时间复杂度为O(n)】 ##

在暴力法中，我们会反复检查一个子字符串是否含有有重复的字符，但这是没有必要的。如果从索引 i 到 j - 1 之间的子字符串 s\{i, j\}已经被检查为没有重复字符。我们只需要检查 s\[j\] 对应的字符是否已经存在于子字符串 s\{i, j\} 中。

要检查一个字符是否已经在子字符串中，我们可以检查整个子字符串，这将产生一个复杂度为 O(n^2)的算法，但我们可以做得更好。通过使用 HashSet 作为滑动窗口，我们可以用 O(1) 的时间来完成对字符是否在当前的子字符串中的检查。

滑动窗口是数组/字符串问题中常用的抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 \[i, j)（左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如，我们将 \[i,j) 向右滑动 1 个元素，则它将变为 \[i+1, j+1)（左闭，右开）。

回到我们的问题，我们使用 HashSet 将字符存储在当前窗口 \[i, j)（最初 j = i）中。 然后我们向右侧滑动索引 j，如果它不在 HashSet 中，我们会继续滑动 j。直到 s\[j\] 已经存在于 HashSet 中。此时，我们找到的没有重复字符的最长子字符串将会以索引 i 开头。如果我们对所有的 i 这样做，就可以得到答案。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1][]

public class LengthOfLongestSubstring_3 {
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            String str = sc.next();
            getLengthOfLongestSubstring3(str);
        }
    
        // 滑动窗口:窗口内的都是已经判断过的没有重复字符的子串，无需重新判断，从而减少判断的次数
        public static int getLengthOfLongestSubstring3(String str) {
            if(str == null && str.length() < 1){
                return 0;
            }
    
            int len = str.length();
            Set<Character> set = new HashSet<>();
            int maxSubLen = 0, i = 0, j = 0;
            // 窗口是从0位置开始的，窗口会慢慢扩大，直到遇见含重复的子串，窗口会减小，处在窗口中的字符都是不重复的，无需再进行判断
            while(i < len && j < len){
                // 扩大[i,j]的范围
                if(!set.contains(str.charAt(j))){
                    // 扩大窗口
                    set.add(str.charAt(j++));
                    maxSubLen = Math.max(maxSubLen, j - i);
                }else{
                    // 减小窗口
                    set.remove(str.charAt(i++));
                }
            }
            System.out.println(maxSubLen);
            return maxSubLen;
        }
    }

**复杂度分析**

*  时间复杂度：O(2n) = O(n)，在最糟糕的情况下，每个字符将被 i 和 j 访问两次。
 *  空间复杂度：O(min(m, n))，与之前的方法相同。滑动窗口法需要 O(k) 的空间，其中 k 表示 `Set` 的大小。而 Set 的大小取决于字符串 n 的大小以及字符集/字母 m 的大小。

--------------------

## 三、优化的滑动窗口 ##

其实对于上诉的滑动窗口的做法还可以做到优化，主要优化的点是：当找到S\[j\] 在 S\{i, j - 1\} 中存在一个重复的字符 j'，这个时候不是让 i++ ，一直超过 j'，而是直接将 i 的位置设置为 j' + 1，跳过 \[i, j'\] 这个范围。相当于遇到重复字符时窗口不是逐渐减小的，而是一步减小到不包含 S\[j\] 的大小。

我们可以使用 HashMap 定义字符到索引的映射，而不是使用集合来判断一个字符是否存在。

[https_leetcode-cn.com_problems_longest-substring-without-repeating-characters]: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
[Link 1]: https://blog.csdn.net/pcwl1206/article/details/89154740
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70]: /images/20220221/d4217066debe482fa9d60bbc039b8bd7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1]: /images/20220221/9bc08c4993c14fc697cfd9a417bc3591.png