《 LeetCode 热题 HOT 100》——无重复字符的最长子串

简介: 《 LeetCode 热题 HOT 100》——无重复字符的最长子串

本期给大家带来的是 LeetCode 热题 HOT 100 第三题关于 无重复字符的最长子串 的讲解。首先,我们还是先从题目入手进行分析思考!!!

题目如下 :👇

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

示例 1:

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

示例 2:

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

示例 3:

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



💥题意分析

本题的意思很简答,就是给出一串字符,让我们算出字符串中 无重复字符的最长子串,最后返回无重复字符串的长度即可!


🔥图解

找出从每一个字符开始的,不包含重复字符的最长子串,那么其中最长的那个字符串即为答案。我们先按照 示例 3 的输出给大家画图解释一下流程:

  • 第一步:

  • 第二步:

  • 第三步:

 

  • 第四步:

  • 第五步:

 

第六步:

当我们进行逐步遍历之后,在把遍历过程中所有的结果进行比较从而找到满足题意的最长的字符串!!!

⭐️  不知道大家从我们上面给的图中是否发现了一件事  ⭐️

    💨 上述流程图,我们每次子串的起始位置递增的往后移动,随着每次起始位置的移动,紧随的我们后面匹配的子串的结束位置也是往后递增的!!!

上述这一点,我们可以从上述图中发现原因:

  • 假设我现在的起始位置就是【第一个的p】的位置,此时它所对应的满足题意的字符串的结束位置为 【第一个w 】的位置

 

 

 

  • 那么当我们选择第  【k+1】个字符的位置作为起始位置时,首先从 【k+1】到 【o】位置此时的字符显然是不重复的,并且由于少了原本的第 【k】 个字符,我们可以继续往后增大 【o】位置,直到右侧出现了重复字符为止

因此,这道题的思想即需要用到有关 滑动窗口 的知识!!

💨 解题思路:

前言:

不知道大家有没有听说过有关 滑动窗口协议 这个知识点。

  • 该协议是 TCP协议 的一种应用,用于网络数据传输时的流量控制,以避免拥塞的发生。该协议允许发送方在停止并等待确认前发送多个数据分组。由于发送方不必每发一个分组就停下来等待确认。因此该协议可以加速数据的传输,提高网络吞吐量。
  • 顾名思义,就像一个滑动的窗口,套在一个序列中,左右的滑动,窗口内就是一个内容集。
  • 通过固定左端元素,再把右端元素不断右移,算出左端和右端间的总数,然后左端再不断右移,不断计算之间的总数。最后算出最小长度。

具体步奏:

  1. 首先我们需要定义两个指针,使用这两个指针表示字符串中的某个子串对应的左右边界,其中左指针代表每次遍历的起始位置,而右指针即为一次遍历中的末尾位置;
  2. 在每次移动的操作中,我们会将左指针向右移动一位,表示我们下次开始遍历过程的起始位置,然后我们可以不断地向右移动右指针进行遍历操作(需要保证两个指针对应的子串中没有重复的字符
  3. 在移动结束后,这个子串就对应着 以左指针开始的,不包含重复字符的最长子串。紧接着我们记录下这个子串的长度
  4. 最后遍历完成之后,比较所有记录下的子串的长度,找到最大的值输出即可!

代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
    //首先对字符串进行判断,如果为空则返回0
     if(s.size() == 0)
     return 0;
    //记录字符出现过,此时需要用到 C++ STL标准库中的 unordered_set 容器
     unordered_set<char> str;
    //用于记录最大的字符串长度,初始化为0
     int MaxLength=0;
     //设置的指针
     int left=-1;
     for(int i=0; i<s.size(); ++i)
     {
         if( i != 0)
         //左指针每次向右移动一位字符,移除一位字符          
              str.erase(s[i-1]);
          
         //去进行遍历查找操作
         while(left +1 < s.size() && !str.count(s[left+1]))
         {
            //不断的向右移动指针     
            str.insert(s[left+1]);           
            left++;
         }
        //此时最大的子串为left位置到 i位置 之间的值
        MaxLength=max(MaxLength,left-i+1);        
     }
     return MaxLength;
    }
};

还有一种方法根据某大佬的写出的:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //首先对字符串进行判断,如果为空则返回0
        if (s.size() == 0)
            return 0;
        //记录字符出现过,此时需要用到 C++ STL标准库中的 unordered_set 容器
        unordered_set<char> str;
        //用于记录最大的字符串长度,初始化为0
        int MaxLength = 0;
        //设置的指针
        int left = 0;
        for (int i = 0; i < s.size(); ++i)
        {
 
            //lookup.find() 查找对应元素,成功返回对应的迭代器,失败返回最后一个元素迭代器(即 lookup.end() )
            while (left + 1 < s.size() && str.find(s[i]) != str.end())
            {
                //不断从左缩小窗口,直到窗口中不存在与下一个字符重复的字符
                str.erase(s[left]);
                left++;
            }
            //此时最大的子串为 i位置 到left位置之间的元素个数
            MaxLength = max(MaxLength, i - left + 1);
            //不断的向右移动指针
            str.insert(s[i]);
        }
        return MaxLength;
    }
};

到此,关于本题的讲解就到这里了!!

相关文章
|
21天前
|
存储 算法
Leetcode第三题(无重复字符的最长子串)
这篇文章介绍了解决LeetCode第三题“无重复字符的最长子串”的算法,使用滑动窗口技术来找出给定字符串中最长的不含重复字符的子串,并提供了详细的代码实现和解释。
54 0
Leetcode第三题(无重复字符的最长子串)
|
3月前
|
算法
LeetCode第3题无重复字符的最长子串
该文章介绍了 LeetCode 第 3 题无重复字符的最长子串的解法,通过使用 HashSet 记录不重复的子元素,以每个字符开头遍历字符串,遇到重复字符则重新计算,最终找到最长子串,同时提到可以考虑使用 HashMap 降低复杂度。
LeetCode第3题无重复字符的最长子串
|
5月前
|
存储 算法 数据可视化
深入解析力扣161题:相隔为 1 的编辑距离(逐字符比较与动态规划详解)
深入解析力扣161题:相隔为 1 的编辑距离(逐字符比较与动态规划详解)
|
4月前
|
索引
821.字符的最短距离-力扣(LeetCode)
821.字符的最短距离-力扣(LeetCode)
31 0
|
5月前
|
存储 算法 程序员
力扣经典150题第三十一题:无重复字符的最长子串
力扣经典150题第三十一题:无重复字符的最长子串
29 0
|
5月前
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
52 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
102 2
|
2月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口