LeetCode 3.无重复字符的最长子串(滑动窗口、双指针)

上一篇博客:LeetCode 2.两数相加(单链表、高精度)

 写在前面:大家好!我是ACfun,我的昵称来自两个单词Acceptedfun。我是一个热爱ACM的蒟蒻。最近萌生了刷LeetCode的想法,所以我打算从LeetCode简单的题目开始做起,攻陷LeetCode。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正,感谢大家的不吝赐教。我的唯一博客更新地址是:https://ac-fun.blog.csdn.net/。非常感谢大家的支持。一起加油,冲鸭!
用知识改变命运,用知识成就未来!加油 (ง •̀o•́)ง (ง •̀o•́)ง

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

文章目录题目信息题目描述示例题解解题思路时间复杂度分析解题代码提交情况

题目信息
题目描述

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

示例

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。

示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。

示例 3:

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

题解
解题思路

 我们可以使用滑动窗口算法(也叫尺取法、双指针算法)滑动窗口算法可以用以解决 数组 或者 字符串 的子元素问题,它可以将嵌套的循环问题,转换为单循环问题,降低时间复杂度。下一篇博客我们在好好的整理一下这个算法。
使用滑动窗口算法枚举所有符合题意的情况,不断的将符合情况的子串进行长度比较,最后一定可以找到那个无重复的最长子串。我们首先初始化左右端点 i 和 j 为 0,然后使右端点 i 向右走,为了方便统计在当前窗口中该字符的个数,我们将当前遍历的字符加到一个哈希表中,使该字符作为哈希表的键,出现的次数作为值。如果值超过1,说明不符合题意,那么我们就不断地将左指针 j 想右移动,不断的缩小窗口,直到窗口中的子串满足题意为止。满足之后我们在使右指针向右移动判断是否满足情况,每次遍历的时候我们都当前的长度 i – j + 1 与最长的长度 ans(初始化为0) 进行比较。遍历完之后即可找到最长的不重复的字串。
LeetCode 3.无重复字符的最长子串(滑动窗口、双指针)
LeetCode 3.无重复字符的最长子串(滑动窗口、双指针)

LeetCode 3.无重复字符的最长子串(滑动窗口、双指针)
LeetCode 3.无重复字符的最长子串(滑动窗口、双指针)
LeetCode 3.无重复字符的最长子串(滑动窗口、双指针)
LeetCode 3.无重复字符的最长子串(滑动窗口、双指针)
LeetCode 3.无重复字符的最长子串(滑动窗口、双指针)
LeetCode 3.无重复字符的最长子串(滑动窗口、双指针)
LeetCode 3.无重复字符的最长子串(滑动窗口、双指针)
LeetCode 3.无重复字符的最长子串(滑动窗口、双指针)
LeetCode 3.无重复字符的最长子串(滑动窗口、双指针)
LeetCode 3.无重复字符的最长子串(滑动窗口、双指针)
LeetCode 3.无重复字符的最长子串(滑动窗口、双指针)
LeetCode 3.无重复字符的最长子串(滑动窗口、双指针)
LeetCode 3.无重复字符的最长子串(滑动窗口、双指针)

LeetCode 3.无重复字符的最长子串(滑动窗口、双指针)
在窗口移动的过程中不断的更新比较最长的长度 ans,最后返回 ans 即可。

时间复杂度分析

 时间复杂度:O(N)
 假设字符的长度为 N,那么左右指针分别会遍历字符串一次,所以时间复杂度为O(N)。

解题代码

class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> map;
int ans = 0;
for (int i = 0, j = 0; i < s.size(); i++) {
map[s[i]]++;
while (map[s[i]] > 1) map[s[j++]]--;
ans = max(ans, i - j + 1);
}
return ans;
}
};

 解释:map[s[j++]]--;的意思是将指针j 向后移动一位,同时将该字符的个数减一,也就是相当于将该字符从当前窗口中移除了。等到之后再遍历到该字符时还会进行加一操作,以此来判断当前窗口的字串是否满足题目条件。

提交情况

LeetCode 3.无重复字符的最长子串(滑动窗口、双指针)

未完待续,持续更新中……
LeetCode 3.无重复字符的最长子串(滑动窗口、双指针)

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

LeetCode 3.无重复字符的最长子串(滑动窗口、双指针)

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » LeetCode 3.无重复字符的最长子串(滑动窗口、双指针)
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏