0


LeetCode 热题 HOT 100 -> 3. 无重复字符的最长子串

题干描述:

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

LeetCode原题链接https://leetcode.cn/problems/longest-substring-without-repeating-characters/



方法1:滑动窗口

方法1分析:

这是经典的滑动窗口类型的题目,几乎是有固定套路:确定一个区间,对这个区间进行某些操作,然后通过操作改变区间的位置和大小,从而解决问题。

具体到这道题上面就是:设置指针** i 从头开始遍历,在 i 之前如果有与 i 相同的字符(命名为same),则无重复字符串的长度就变为 same 的下一个字符到 i的长度。下一趟循环也只需从same 的下一个字符开始判断,即 same+1 到 i **(这里的 i 是 i++ 之后的 i )这个区间。

代码如下 :

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int size = s.size();
        int MaxLen = 0; //记录最大长度
        int same=0; //用来寻找在i下标之前与s[i]相同的字符
        int begin=0; //记录无重复字符串的首位置
        for (int i = 0; i < size; i++) //每一趟循环都是在记录以i结尾的最长无重复字符串的长度
        {
            for(same = begin ; same < i ; same++)
            {
                if(s[same]==s[i])
                {
                    begin=same+1;
                    break;
                }
            }
            MaxLen=max(MaxLen,i-begin+1); //记录以i下标结尾的无重复字符串的长度
        }
        return MaxLen;
    }
};

复杂度分析 :

时间复杂度:O(N^2),两层循环。

空间复杂度:O(1),只开了常数个空间。


方法2:用哈希集合来优化滑动窗口

方法2分析:

方法1中我们使用循环来查找是否在之前有相同元素,这种使用循环查找的方法时间复杂度为O(N),我们很容易想到使用unordered_set(哈希集合)便能够使“查找之前是否有相同元素”这件事情的时间复杂度变为O(1),是典型的用空间换时间的做法。但是整个的执行流程需要稍作修改,看注释即可。

**代码如下: **

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int size = s.size();
        unordered_set<char> lookup; //创建一个哈希集合
        int MaxLen = 0; //记录最大长度
        int end = 0; //标记无重复字符串的最后一个位置
        for (int i = 0; i < size; i++) //i用来标记无重复字符串的首位置,每一趟循环都是在记录以i开头的最长无重复字符串的长度
        {
            while (end < size && lookup.count(s[end]) == 0)
            {
                lookup.insert(s[end]); //如果之前没有重复的字符,则将该字符加入集合中,并使end后移1位
                end++;
            }
            MaxLen = max(MaxLen, end - i); 
            lookup.erase(s[i]); //删除s[i],即以i开头的最长无重复字符串的长度已经计算完成
        }
        return MaxLen;
    }
};

复杂度分析:

时间复杂度:O(N),下标** i 和下标 end** 分别遍历了一遍字符串,循环执行了2N次。

空间复杂度:O(N),unordered_set开了O(N)的空间。


该题的分享就到这里,本人才疏学浅,肯定会有错误或考虑不周到的地方,如有纠错或建议,非常欢迎在评论区留言,我看见后会立刻回复并在思考后对文章作出合适的修改,感谢阅读~

标签: leetcode 算法 c++

本文转载自: https://blog.csdn.net/HitoriOVO/article/details/125404555
版权归原作者 想进大厂的小皓同学 所有, 如有侵权,请联系我们删除。

“LeetCode 热题 HOT 100 -> 3. 无重复字符的最长子串”的评论:

还没有评论