「Leetcode」滑动窗口—无重复字符的最长子串

2023-12-13 21:26:33
在这里插入图片描述


📄题目

3. 无重复字符的最长子串

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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

  • 0 ≤ s . l e n g t h ≤ 5 ? 104 0 \le s.length \le 5 * 104 0s.length5?104
  • s 由英文字母、数字、符号和空格组成

??题目解析 & 思路

暴力法
我们在考虑滑动窗口前,可以先想下暴力法的解决办法,然后再优化推演出滑动窗口的解法。本题的暴力法非常的简单,只需用两层循环来遍历数组,如果找到了重复的字符,则更新结果,再进到下一层循环,因为我们需要知道遍历的结果是否重复,所以此题需要用到哈希表来记录遍历的结果。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size(), ret = 0;	
        unordered_map<int, int> map;	//也可以使用数组来代替

        for(int left = 0; left < n; ++left)
        {
            map.clear();		//清除上一轮循环的影响
            for(int right = left; right < n; ++right)
            {
                map[s[right]]++;		//更新哈希表
                if(map[s[right]] > 1)	//发现重复字符,推出循环
                    break;

                ret = max(ret, right-left+1);	//更新状态
            }
        }
        return ret;
    }
};

时间复杂度: O ( n 2 ) O(n^2) O(n2)
空间复杂度: O ( 1 ) O(1) O(1) (空间最多为字符集的个数)

滑动窗口
再暴力法中可以发现,在 r i g h t right right 遇到重复字符时便退出了循环,重新在 l e f t left left 的下一个位置继续遍历,我们可以发现重复在这轮循环中重复遍历了不少上一次循环的字符,那么我们就可以在这里进行优化。

做滑动窗口的步骤:

  1. 进窗口
  2. 判断
    • 出窗口
  3. 更新结果状态
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size(), ret = 0;
        unordered_map<int, int> map;
        for(int left = 0, right = 0; right < n; ++right)	
        {
            map[s[right]]++;	//进窗口
            while(map[s[right]] > 1)	//判断是否重复
                map[s[left++]]--;		//出窗口
                
            ret = max(ret, right-left+1);	//更新结果状态
        }

        return ret;			//返回结果
    }
};

时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)

📓总结

📜博客主页:主页
📫我的专栏:C++
📱我的github:github

文章来源:https://blog.csdn.net/CaTianRi/article/details/134966003
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。