当前位置: 首页> 健康> 养生 > 少儿编程培训机构哪家好_西安最有名的策划公司_网络营销课程主要讲什么内容_好网站

少儿编程培训机构哪家好_西安最有名的策划公司_网络营销课程主要讲什么内容_好网站

时间:2025/7/11 15:31:36来源:https://blog.csdn.net/2301_79796701/article/details/143451343 浏览次数:0次
少儿编程培训机构哪家好_西安最有名的策划公司_网络营销课程主要讲什么内容_好网站

目录

题目

题解


题目

3. 无重复字符的最长子串 - 力扣(LeetCode)

题解

        暴力解法是用两层循环列举出所有可能,并用O(N)的空间复杂度存储临时的字符来判断某个区间是否重复了。

        空间复杂度上我们可以用一个哈希表,把空间复杂度降为O(1)。哈希表中存储某个区间字符和字符出现的次数的映射,但我们不必真的定义一个std::unordered_map<char, int>。我们可以int hash[128]代替。

        时间复杂度上,我们只需维护一个窗口。算法如下

        1.入窗口,把字符映射到hash[128]。

        2.判断:

如果这个字符出现的频次超过 1 ,说明窗⼝内有重复元素,那么就从左侧开始划出窗⼝,
直到 ch 这个元素的频次变为 1 ,然后再更新结果。
如果没有超过 1 ,说明当前窗⼝没有重复元素,可以直接更新结果
代码如下:
class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] = {0}; int left = 0;int right = 0;int s_len = s.size();int ret = 0;while (right < s_len) {hash[s[right]]++; //入窗口while (hash[s[right]] > 1)  hash[s[left++]]--;ret = max(ret, right - left + 1);right++;}return ret;}
};
关键字:少儿编程培训机构哪家好_西安最有名的策划公司_网络营销课程主要讲什么内容_好网站

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: