Loading [MathJax]/jax/input/TeX/jax.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >LeetCode第三题,五个版本迭代优化带你吃透two pointers算法

LeetCode第三题,五个版本迭代优化带你吃透two pointers算法

作者头像
TechFlow-承志
发布于 2022-08-26 10:11:26
发布于 2022-08-26 10:11:26
43300
代码可运行
举报
文章被收录于专栏:TechFlowTechFlow
运行总次数:0
代码可运行

作者 | 梁唐

大家好,我是梁唐。

今天给大家带来LeetCode第三题的题解——无重复字符的最长子串,题意等描述来源于力扣官网。

题意

给定一个字符串s,要求返回其中不包含重复字符的最长子串的长度。

样例

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

数据范围

0s.length5104
  • s由英文字母、数字以及符号和空格组成

解法

拿到题目首先分析题意,题意还是比较简单的,就是要找最长的不含有重复字符的子串。

枚举

很容易想到我们可以枚举,首先我们可以枚举出s的所有子串,然后再一一判断子串当中是否包含重复的字符。最后选择不含有重复字符的最大子串即可。

写出代码来的话大概就是这样:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
int n = s.size();
maxi = 0;

bool check(string &s, int st, int end) {
    set<char> st;
    for (int i = st; i <= end; i++) {
        if (st.count(s[i])) {
            return false;
        }
        st.add(s[i]);
    }
    return true;
}

for (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
        if (check(s, i, j) && j-i+1 > maxi) {
            maxi = j-i+1;
        }
    }
}
return maxi;

如果大家去提交就会发现,这样的代码无法通过测试。我们简单分析一下就会发现这个算法的复杂度太大了,因为我们里外里一共用了三重循环。两重循环用来枚举子串的开头和结尾,还有一重循环判断子串是否包含重复字符。

我们知道s的长度最大是1e4,

O(n3)

的量级下,计算复杂度大约是1e12这个量级,显然会严重超时,必须要进行优化。

怎么优化呢?首先我们可以想到,我们其实没有必要枚举子串的开头和结尾,只需要枚举开头,在保证不包含重复字符的前提下往末尾一位一位延伸,直到结束或者是遇到重复字符为止。这样的话,我们就可以去掉一重循环,复杂度可以降到

O(n2)

,1e8的量级勉强不会超时。

代码如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ret = 0;
        // 枚举子串开头
        for (int i = 0; i < s.length(); i++) {
            set<char> st;
            // 一位一位地加入字符,直到出现重复break
            for (int j = i; j < s.length(); j++) {
                if (st.count(s[j])) {
                    break;
                }else {
                    st.insert(s[j]);
                    ret = max(ret, j - i + 1);
                }
            }
        }
        return ret;
    }
};

two pointers

如果大家学过two pointers算法的话,会发现这题就是two pointers的模板题。所谓模板题就是只要简单套用算法就可以求解的题目。

two pointers算法翻译过来就是两指针算法,非常非常地简单,其实可以理解成区间维护算法。我们用两个变量ij分别指向一段区间的开头和结尾,保证这个区间是以i开头、j结尾能够找到的最大合法区间。

然后我们把j往右移动一位,由于j移动了之后带入了新的元素s[j+1],可能会导致区间合法性的破坏。

前面说了我们要保证区间是合法的,合法性破坏了我们需要想办法恢复它的合法性。我们可以移动i,把i也往右移动,弹出元素,直到区间恢复合法性。

比如移动之后i变动到了k,区间[k, j+1]是新的合法区间。两指针算法其实就是这样两个指针交替移动保证区间一直合法的算法。

算法是很简单,但是我们对于算法的分析却远远没有结束。其实稍微细想一下,会发现几个问题。第一个问题是,我们迭代的合法区间的第一个版本从哪里来?第二个问题是,如何可以保证我们一定能够找到最大的那个合法区间呢?第三个问题是这个算法的复杂度是多少?

第一个问题比较简单,很明显,对于本题来说,[0, 0]就是一个合法区间。对于只有一个元素的区间,一定是合法的。

第二个问题则困难许多,是一道证明题,也就是得证明我们的算法一定会覆盖最大的合法区间。怎么证明呢?我们可以利用一些前提条件。

我们前文当中有一个设定,[i, j]是以i为开头和以j为结尾所能找到的最大合法区间。当我们将j移动到j+1之后,找到的新的合法区间[k, j+1],其中的k一定大于等于i。不然的话就和我们的假设矛盾了。可能大家会觉得有些乱,没有关系,我们可以简化一下只看变量j。我们很容易发现,不论j如何移动,当前的合法区间一定都是以j结尾能找到的最大合法区间。

我们枚举了所有的j,自然可以保证全局的最大合法区间也在其中。把这些都想明白了,其实代码就很好写了:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ret = 0;
        set<char> st;
        int l = 0, r = 0;

        for (r = 0; r < s.length(); r++) {
            // 判断区间是否非法
            if (st.count(s[r])) {
                // 如果非法,将区间左侧右移,弹出元素
                while (st.count(s[r])) {
                    st.erase(s[l++]);
                }
            }
            ret = max(ret, r-l+1);
            st.insert(s[r]);
        }
        return ret;
    }
};

two pointers算法的复杂度是O(n),估计很多同学会觉得很奇怪。明明代码里用了两重循环,为什么还是O(n)的复杂度呢?

我们稍微分析一下就会发现,l和r都是递增的变量,并且每执行一次循环,都会触发l或者r的增加。由于l和r最多只能从0增到n,所以加起来就是2n次操作。所以虽然我们用了两重循环,但依然是一个O(n)的算法。

优化

在这个实现当中,我们是用了一个set判断字符是否出现重复。其实我们还有更快的做法,是可以优化的。因为题目当中明确说了,字符只会有英文字符以及标点符号和数字。也就是说出现的字符是一个char类型,我们都知道char类型本质是整型,它的范围不会超过256。

所以我们可以使用一个长度为256的数组来代替set,因为数组的查询以及修改速度更快,可以达到O(1)

经过优化之后,我们的代码是这样:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ret = 0;
        int st[256] = {0};
        int l = 0, r = 0;

        for (r = 0; r < s.length(); r++) {
            // 判断区间是否非法
            if (st[s[r]]) {
                // 如果非法,将区间左侧右移,弹出元素
                while (st[s[r]]) {
                    st[s[l++]]--;
                }
            }
            ret = max(ret, r-l+1);
            st[s[r]]++;
        }
        return ret;
    }
};

但是到这里还没有结束,这段算法依然还有优化的空间。

我们看一下会注意到我们用到了两重循环,其实仔细思考一下会发现内部的循环是可以去掉的。怎么去呢?

首先,我们思考一下里面while循环的用途,是为了弹出区间左侧的字符,使得s[r]这个字符在区间当中不再出现,只有这样才能将s[r]加入区间。

其实我们完全可以用数组记录下区间里的每一个字符出现的位置,当出现冲突的时候,我们就可以直接找到合法的位置了。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ret = 0;
        int st[256];
        memset(st, -1, sizeof st);

        int l = 0, r = 0;

        for (r = 0; r < s.length(); r++) {
            char c = s[r];
            // st[c] >= l 即c字符在区间当中出现过
            if (st[c] >= l) {
                // 将l移动到c字符的后一位即可
                l = st[c] + 1;
            }            
            st[c] = r;
            ret = max(ret, r-l+1);
        }
        return ret;
    }
};

有几个细节需要注意一下,首先是数组st的初始化,全部初始化成-1,而不是0。因为0是有实际含义的,代表第0位的字符。其次是循环内部的判断,由于我们数组记录的不再是字符出现的次数而是字符出现的位置。

所以我们的判断条件也要修改,改成当前字符最后一次出现的位置是否大于现在的左侧边界l。如果最后一次出现的位置大于l,说明这个字符一定在当前的区间当中,也就是说会构成重复,需要移动l。很明显,要使得每个字符都不重复,l必须移动到该位置的右侧,最近的位置自然就是st[c] + 1

虽然这道题不算很难,代码也很好写,但其中的思路以及一层一层优化迭代的技巧还是非常有价值的。因此非常推荐大家每一种解法都亲自试一试,体会一下其中的差别。

单纯地刷题是无法学好算法的,刷题之余的深入思考是必不可少的。

大家加油,与你们共勉!

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-11-20,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Coder梁 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
学会two pointers算法,玩转LeetCode
今天给大家聊一个非常经典也非常简单的算法,学会了这个算法不说能够纵横leetcode,但可以解决非常多的问题。并且很多其他的算法也用到了类似的思想,非常有借鉴意义。
TechFlow-承志
2022/08/26
2610
学会two pointers算法,玩转LeetCode
【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串
索引从字符串的第一位开始,将后面的字符依次加入到 set 里面。如果 set 里面已经有了该字符,此次循环结束,内循环结束后记录 size。字符串的每一位都用这种方法去计算,得到的最大的 size 即是答案。
帅地
2019/12/19
7920
【图解】三种解法不断优化带你手撕 LeetCode第三号题:无重复字符的最长子串
每日一题:LeetCode-LCR 016. 无重复字符的最长子串
   🔎🔎如果说代码有灵魂,那么它的灵魂一定是👉👉算法👈👈,因此,想要写出💚优美的程序💚,核心算法是必不可少的,少年,你渴望力量吗😆😆,想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长的道路🏇🏇,我们要做的,就是斩妖除魔💥💥,打怪升级!💪💪当然切记不可😈走火入魔😈,每日打怪,拾取经验,终能成圣🙏🙏!开启我们今天的斩妖之旅吧!✈️✈️
用户11029129
2024/06/04
1150
每日一题:LeetCode-LCR 016. 无重复字符的最长子串
LeetCode热题100(滑动窗口篇)
这种子串子数组问题,而且还满足窗口的右边界右移动就是加,左边界右移就是减的问题大概率就是滑动窗口。
Yui_
2025/01/17
1160
LeetCode热题100(滑动窗口篇)
LeetCode 刷题笔记——day 2
思路:通过数组下标方式遍历字符串并逐个比较,需要考虑非常多种可能的输入。(多次修改后最终用经典暴力求解法得出(也许)准确的答案)
h-t-m
2022/11/22
3760
LeetCode 第3题 无重复字符的最长子串(小白详解)
输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。
地鼠窝里有个Gopher
2022/10/30
2900
LeetCode3 一题学会尺取算法
我们先从最简单的方法开始,最容易想到的算法就是暴力枚举。我们可以遍历出这个字符串当中所有的子串,之后再判断这个子串当中有没有出现重复的元素。如果没有重复的元素,那么我们就更新答案。
TechFlow-承志
2020/03/05
4750
LeetCode3 一题学会尺取算法
LeetCode算法题 顶
第1题https://leetcode-cn.com/problems/two-sum/
算法之名
2020/03/19
3200
刷题日常(移动零,盛最多水的容器,三数之和,无重复字符的最长子串)
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
用户11369558
2024/12/24
820
刷题日常(移动零,盛最多水的容器,三数之和,无重复字符的最长子串)
【刷穿 LeetCode】3. 无重复字符的最长子串(中等)
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
宫水三叶的刷题日记
2021/02/20
4050
【优选算法】——滑动窗口——3. 无重复字符的最长子串
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。(即为连续的)
小李很执着
2024/06/15
2500
【优选算法】——滑动窗口——3. 无重复字符的最长子串
程序员进阶之算法练习(四十八)LeetCode
题目链接 题目大意: 给出两个非空的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。 如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
落影
2020/10/27
4240
程序员进阶之算法练习(四十八)LeetCode
既是「滑动窗口」入门题,更是高频面试题 ...
这是 LeetCode 上的「3. 无重复字符的最长子串」,难度为 「Medium」。
宫水三叶的刷题日记
2021/02/26
4920
【Day34】LeetCode算法 -- 3. 无重复字符的最长子串
解题思路: 题目会给定一个字符串s,我们需要返回其中最长子串的长度,注意,这里返回的是最长子串长度而非最长子序列长度。例如:“abbcde”,最长子串是“bcde” ; 最长子序列是“abcde” ;
.29.
2022/11/15
2160
【Day34】LeetCode算法 -- 3. 无重复字符的最长子串
LeetCode-题库-刷题(1-3)
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。 具体题目链接
布衣者
2021/09/07
7690
三分钟算法修行-无重复字符的最长子串的《四种解法》
  最近有小伙伴和我谈心,觉得刷算法题太难了,完全没有思路,很有挫败感,想要放弃了。想想自己也深有感触,有这些想法真都挺正常的,其实我们刷算法就是为了培养一个思考问题、解决问题的思维,这个思维养成并不是一蹴而就的,而是循序渐进的。
IT学习日记
2022/09/13
2.9K0
三分钟算法修行-无重复字符的最长子串的《四种解法》
刷题记录(LeetCode 100 热题系列)2
无重复字符的最长子串 LeetCode url (https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/)
猎户星座1
2021/01/17
3320
003. 无重复字符的最长子串 | Leetcode题解
题目要求连续, 我们考虑使用滑动窗口。而这道题就是窗口大小不固定的滑动窗口题目,然后让我们求满足条件的窗口大小的最大值,这是一种非常常见的滑动窗口题目。
苏南
2020/12/16
5620
003. 无重复字符的最长子串 | Leetcode题解
LeetCode 03无重复字符的最长子串(滑动窗口)
本题选择的思路是滑动窗口,滑动窗口,就是用一个区间从左往右,右侧先进行试探,找到区间无重复最大值,当有重复时左侧再往右侧移动一直到没重复,然后重复进行。在整个过程中找到最大的那个空间返回即可。
bigsai
2020/08/13
7040
LeetCode 03无重复字符的最长子串(滑动窗口)
leetcode刷题(3)——无重复字符的最长子串
输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 示例 2:
老马的编程之旅
2022/06/22
2080
推荐阅读
相关推荐
学会two pointers算法,玩转LeetCode
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验