模块二——滑动窗口:3.无重复字符的最长子串

2023-12-13 03:44:32

题目描述

题目链接:3.无重复字符的最长子串
在这里插入图片描述

算法原理

解法?:暴?求解(不会超时,可以通过)

枚举从每?个位置开始往后,?重复字符的?串可以到达什么位置。找出其中?度最?的即可。
在往后寻找?重复?串能到达的位置时,可以利?哈希表统计出字符出现的频次,来判断什么时候?串出现了重复元素。

解法二:滑动窗口

研究的对象依旧是?段连续的区间,因此继续使?滑动窗?思想来优化。
让滑动窗?满?:窗?内所有元素都是不重复的。
做法:右端元素ch进?窗?的时候,哈希表统计这个字符的频次:

  • 如果这个字符出现的频次超过1 ,说明窗?内有重复元素,那么就从左侧开始划出窗?,直到ch 这个元素的频次变为1 ,然后再更新结果。
  • 如果没有超过1 ,说明当前窗?没有重复元素,可以直接更新结果。

代码实现

解法?:暴?求解(时间复杂度为O(N2),空间复杂度为O(1))

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0;//记录结果
        for(int left = 0;left < s.size();left++)
        {
            int hash[128] = { 0 };//记录每个字母的出现次数
            for(int right = left;right < s.size();right++)
            {
                hash[s[right]]++;
                if( hash[s[right]] > 1)
                {
                    break;
                }
                res = max(res,right - left + 1);
            }
        }
        return res;
    }
};

解法二:滑动窗口(时间复杂度为O(N),空间复杂度为O(1))

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[128] = { 0 };//记录每个字母的出现次数
        int res = 0;//记录结果
        for(int left = 0,right = 0;right < s.size();right++)//1.控制窗口的左右指针
        {
            hash[s[right]]++;//2.进窗口
            while(hash[s[right]] == 2)//3.判断
            {
                //出窗口
                hash[s[left]]--;
                left++;
            }
            res = max(res,right - left + 1);
        }
        return res;
    }
};

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