网站开发教程免费,秀山网站建设公司,上海品牌推广公司,青岛建站开发力扣题目链接#xff1a;无重复字符的最长子串
一、题目解析 二、算法原理
解法一#xff1a;暴力解法#xff08;时间复杂度最坏#xff1a;O(N)#xff09;
从每一个位置开始往后枚举#xff0c;在往后寻找无重复最长子串时#xff0c;可以利用哈希表来统计字符出现…力扣题目链接无重复字符的最长子串
一、题目解析 二、算法原理
解法一暴力解法时间复杂度最坏O(N)
从每一个位置开始往后枚举在往后寻找无重复最长子串时可以利用哈希表来统计字符出现的频率如果出现了重复字符就跳出循环如果没有重复则更新结果这样枚举下去找到长度最长的返回即可。
解法二滑动窗口 滑动窗口也是定义了两个指针在移动但是这两个指针所指向的区间就像一个滑动的窗口一样。 滑动窗口的基本步骤 定义两个指针int left0right0;进入滑动窗口——让字符进入哈希表判断条件——窗口内出现重复字符出滑动窗口——从哈希表中将字符删除更新结果 注结果的更新不一定是放在最后这个要根据题目的要求进行相应的改变而且判断条件是要循环一直判断如果满足就出窗口不满足条件循环才停止。 每次移动指针的时候结果都在更新所以结果不会出错。 时间复杂度虽然代码是两层循环但是left指针和right指针都是不回退的两者最多都往后移动n次。因此时间复杂度是O(N)。 这个题最大的难度是怎么分析这个问题从而想到要用滑动窗口来解决。
三、代码编写
暴力枚举
class Solution {
public:int lengthOfLongestSubstring(string s) {int ret 0;int n s.size();for(int i 0; i n; i){int hash[128] {0};//用数组模拟哈希表统计次数for(int j i; j n; j){hash[s[j]];if(hash[s[j]] 1)//判断是否重复break;ret max(ret, j - i 1);//更新结果}}return ret;}
};
滑动窗口
class Solution {
public:int lengthOfLongestSubstring(string s) {int ret 0;int left 0, right 0, n s.size();int hash[128] {0};//用数组来模拟哈希表while(right n){hash[s[right]];//进窗口while(hash[s[right]] 1)//判断{hash[s[left]]--;//出窗口}ret max(ret, right - left 1);//更新结果right;}return ret;}
};
如有错误或不足欢迎大家批评指正。
