跟我学：LeetCode刷题之3. 无重复字符的最长子串

发表于 分类于 阅读次数：

导读

刷算法题需要一定的节奏，同样对待每一道算法题也需要认真的对待不可操之过急，否则会导致：算法虐我千万遍，我待算法如初恋！如果这句话是从对算法态度上说爱如初恋那必须得肯定你的态度，但如果是每一道算法题，反复都能虐你千万遍，那这个初恋的滋味肯定不好受。我们应该是面对新题对待如初恋，对待已经做过的题应该是勾勾手指，手到擒来的老司机，否则就是白刷。不仅浪费时间而且浪费精力，所以刷题必须讲究方式方法，建议反复阅读此文跟我学：LeetCode刷题大法。下面这里通过一张思维导图帮助大家整理这道题的思路。思维导图一方面罗列了本文的大纲，另一方面也是希望读者朋友可以保存图片至自己的复习资料里，以便随时通过该大纲去复习，注意关注标红的重点解法。

跟我学：LeetCode刷题之3. 无重复字符的最长子串

看题总结

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

示例 1:

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

示例 2:

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

示例 3:

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

Related Topics

哈希表

双指针

字符串

Sliding Window

通过对题目的阅读，我们可以得出以下几个结论

  1. 题目类型为数组
  2. 要求是返回最长的不含重复字母的子串长度
  3. 输入的字符串可能为空串，输入判断

多解法及复杂度分析

解法一：暴力法，多重循环

首先希望读者能写出双重循环的模板代码，在此再次强调此代码是数组问题暴力法的套路墙裂建议背诵默写，如果还是不能随手写出回过头看一下此文跟我学：LeetCode刷题之1.两数之和，好了继续此问题的暴力解决法就是通过双重循环，加内部一层循环判断[i,j]之间的元素是否是唯一的，然后做相应的移动和记录最大值。注意此处的双重循环的i，j范围，是由于allUnique()方法的for循环范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j <= n; j++)
                if (allUnique(s, i, j)) ans = Math.max(ans, j - i);
        return ans;
    }

    public boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        for (int i = start; i < end; i++) {
            Character ch = s.charAt(i);
            if (set.contains(ch)) return false;
            set.add(ch);
        }
        return true;
    }

复杂度分析

时间复杂度：O(n^3)，三重循环

空间复杂度：O(min(n, m))O(min(n,m))，我们需要 O(k)的空间来检查子字符串中是否有重复字符，其中 k 表示 Set 的大小。而 Set 的大小取决于字符串 n 的大小以及字符集/字母 m 的大小。

解法二：双指针+滑动串口

该题的实现思路主要是基于：滑动窗口。

什么是滑动窗口？

其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

如何移动？

我们只要把队列的左边的元素移出就行了，直到满足题目要求！如左出右进变为bca

一直维持这样的队列，找出队列出现最长的长度时候，求出解！

  • 哈希法的实现可以基于Map定义key为字符串的中的每个字符，value为该字符的位置i+1(方便计算长度）
  • 通过数组实现，应为字符串由字母组成所以可以根据ASCII码的字符大小128，存放字符的位置i+1。

这里推荐使用数组，数组的存取都是O(1)的实现，当然Map在此种情况下也是的。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] hash = new int[128];
        int start = 0;
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            start = Math.max(ans, hash[s.charAt(i)]);
            ans = Math.max(ans, i - start + 1);
            hash[s.charAt(i)] = i + 1;
        }
        return ans;
    }

复杂度分析

时间复杂度：O(n)，只进行一次遍历

空间复杂度：O(m)，m 是字符集的大小128

两种解法，充分体现了以空间换时间思想的，来一次加快算法处理速度。所以在算法题中哈希表数组和Map的代码也需要背诵记忆，才能游刃有余。

同类题相关

992. K 个不同整数的子数组

若你反复AC，且充分理解了本题解法，可以尝试去解答同类题992该题是困难题不过无妨，同类题的意思就是变形，往往是增加了特定的条件或者是针对不同的场景。所以同类题的目的是，透过现象看本质，一时的解不出不碍事，按我说的方法跟我学：LeetCode刷题大法，通过此种方法一定是越来越自信的刷题。

技巧与心得

  1. 开一个github仓库用来记录各种题解
  2. 在idea或者vscode中都提供了leecode的插件刷题，方便调试断走流程
  3. 遇到不会的题不要慌，稳住心态直接看题解
  4. 文字类的表述不如视图类的直观，图文并茂精选图解优先或者参考leetcode国际站的大牛题解
  5. 图解依旧看着吃力也无妨，可以在哔哩哔哩或者YouTube上，通过leecode + 题号，搜索高收视率的视频观看
  6. 多看几次本文跟我学：跟我学：LeetCode刷题大法，相信我你肯定能越刷越自信

最后的最后

看到最后，我相信你对本题应该有不一样的感受了吧！在此若有不对之处或建议等，留言告诉我；若有疑惑或者不一样的看法，也请告诉我，我们可以一起探讨学习！

我是Yangcy，该吃吃该喝喝，该学还得学，我们一起加油！