专栏首页小浩算法漫画:滑动窗口系列 第二讲(无重复字符的最长子串)

漫画:滑动窗口系列 第二讲(无重复字符的最长子串)

在上一节中,我们使用双端队列完成了滑动窗口的一道颇为困难的题目,以此展示了什么是滑动窗口。在本节中我们将继续深入分析,探索滑动窗口题型一些具有模式性的解法。

01 滑动窗口介绍

对于大部分滑动窗口类型的题目,一般是考察字符串的匹配。比较标准的题目,会给出一个模式串B,以及一个目标串A。然后提出问题,找到A中符合对B一些限定规则的子串或者对A一些限定规则的结果,最终再将搜索出的子串完成题意中要求的组合或者其他

比如:给定一个字符串 s 和一个非空字符串 p,找到 s 中所有是 p 的字母异位词的子串,返回这些子串的起始索引。

又或者:给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字母的最小子串。

再如:给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

都是属于这一类的标准题型。而对于这一类题目,我们常用的解题思路,是去维护一个可变长度的滑动窗口。无论是使用双指针,还是使用双端队列,又或者用游标等其他奇技淫巧,目的都是一样的。

Now,我们通过一道题目来进行具体学习:

02 第3题:无重复字符的最长子串

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

示例 1:

输入: "abcabcbb"

输出: 3

解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: "bbbbb"

输出: 1

解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: "pwwkew"

输出: 3

解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。

请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

03 题解分析

直接分析题目,假设我们的输入为“abcabcbb”,我们只需要维护一个窗口在输入字符串中进行移动。如下图:

当下一个元素在窗口没有出现过时,我们扩大窗口。

当下一个元素在窗口中出现过时,我们缩小窗口,将出现过的元素以及其左边的元素统统移出:

在整个过程中,我们记录下窗口出现过的最大值即可。而我们唯一要做的,只需要尽可能扩大窗口

那我们代码中通过什么来维护这样的一个窗口呢?anyway~ 不管是队列,双指针,甚至通过map来做,都可以。

我们演示一个双指针的做法:

//java
public class Solution {
    public static int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int result = 0, left = 0, right = 0;
        while (left < n && right < n) {
            //charAt:返回指定位置处的字符
            if (!set.contains(s.charAt(right))) {
                set.add(s.charAt(right));
                right++;
                result = Math.max(result, right - left);
            } else {
                set.remove(s.charAt(left));
                left++;
            }
        }
        return result;
    }
}

通过观察,我们能看出来。如果是最坏情况的话,我们每一个字符都可能会访问两次,left一次,right一次,时间复杂度达到了O(2N),这是不可饶恕的。不理解的话看下图:

假设我们的字符串为“abcdc”,对于abc我们都访问了2次。

那如何来进一步优化呢?

其实我们可以定义字符到索引的映射,而不是简单通过一个集合来判断字符是否存在。这样的话,当我们找到重复的字符时,我们可以立即跳过该窗口,而不需要对之前的元素进行再次访问。

//java
public class Solution {
    public static int lengthOfLongestSubstring(String s) {
        int n = s.length(), result = 0;
        Map<Character, Integer> map = new HashMap<>(); 
        for (int right = 0, left = 0; right < n; right++) {
            if (map.containsKey(s.charAt(right))) {
                left = Math.max(map.get(s.charAt(right)), left);
            }
            result = Math.max(result, right - left + 1);
            map.put(s.charAt(right), right + 1);
        }
        return result;
    }
}

修改之后,我们发现虽然时间复杂度有了一定提高,但是还是比较慢!如何更进一步的优化呢?我们可以使用一个256位的数组来替代hashmap,以进行优化。(因为ASCII码表里的字符总共有128个。ASCII码的长度是一个字节,8位,理论上可以表示256个字符,但是许多时候只谈128个。具体原因可以下去自行学习~)

//java
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        int result = 0;
        int[] charIndex = new int[256];
        for (int left = 0, right = 0; right < len; right++) {
            char c = s.charAt(right);
            left = Math.max(charIndex[c], left);
            result = Math.max(result, right - left + 1);
            charIndex[c] = right + 1;
        }
        return result;
    }
}

我们发现优化后时间复杂度有了极大的改善!这里简单说一下原因,对于数组和hashmap访问时,两个谁快谁慢不是一定的,需要思考hashmap的底层实现,以及数据量大小。但是在这里,因为已知了待访问数据的下标,可以直接寻址,所以极大的缩短了查询时间。

04 啰啰嗦嗦

本题基本就到这里。最后要说的,一般建议如果要分析一道题,我们要压缩压缩再压缩,抽茧剥丝一样走到最后,尽可能的完成对题目的优化。不一定非要自己想到最优解,但绝对不要局限于单纯的完成题目,那样将毫无意义!

最后,原创文章实在不易...希望大家可以帮忙转发~不胜感激~(记得打卡)

转发是对我最大的支持!

注:本系列所有教程中都不会用到复杂的语言特性,大家不需要担心没有学过语法知识。算法思想最重要,使用各语言纯属本人爱好。同时,本系列所有代码均在leetcode上进行过测试运行,保证其严谨性!

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员浩哥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 漫画:反转字符串

    今天是初一,因为新型肺炎外出的活动基本都取消了,待在家里学习看书陪陪家人。希望大家也提高意识,能不出门就尽量别出了!

    程序员小浩
  • 漫画:一文看懂螺旋矩阵求解

    第54题:定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。

    程序员小浩
  • 漫画:如何使用二分法回滚代码?

    一般我们使用 git reset --hard #version 来进行回滚到指定版本的代码。

    程序员小浩
  • 算法:快速排序以及第k小元素的线性选择算法

    简要介绍下快速排序的思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行...

    s1mba
  • 你所能用到的数据结构(一)

         无损编码的霍夫曼编码以及其余的各种编码由于要使用比较复杂的数据结构,所以按照我昨天说的,我决定从数据结构开始写起。数据结构和算法很难完全的分开,好的数...

    一心一怿
  • python冒泡法排序算法

    冒泡法排序思想:将数组中的数据两两进行比较,每次将较大的数据交换到后面,直到大数沉底,小数冒出。

    py3study
  • 相机标定黑白格纸生成(提供PDF版下载)

    小白近期对相机进行了标定,关于相机标定的原理和方法网上比较多,讲解也比较详细,这里小白也就不再重复,如果有对原理不是很清晰的小伙伴,可以后台私密我。

    小白学视觉
  • 167. 两数之和 II - 输入有序数组

    函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。

    村雨遥
  • 6 月编程语言排行榜:Python 飙升,有望挑战 Java 和 C?

    排名前三变成了 Java、C、Python,C++ 掉到第四,第五为 VB .NET。

    老九君
  • sofa-rpc负载均衡之随机算法分析(Random)

                                                 图1 RandomLoadBanlancer的类继承图

    克虏伯

扫码关注云+社区

领取腾讯云代金券