当前位置：网站首页>LeetCode 热题 HOT 100 -＞ 3. 无重复字符的最长子串

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

2022-07-28 00:49:00 【想进大厂的小皓同学】

题干描述：
给定一个字符串 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;
    }
};