哪类小网站容易做,北沙滩网站建设,深圳网站建设网页推广网站设计,工商查询题目链接
力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台 题目解析
从s字符串中#xff0c;去找出连续的子串#xff0c;使该子串中没有重复字符#xff0c;返回它的最长长度。
暴力枚举 依次以第一个、第二个、第三个等等为起点去遍历字符串LeetCode官网 - 全球极客挚爱的技术成长平台 题目解析
从s字符串中去找出连续的子串使该子串中没有重复字符返回它的最长长度。
暴力枚举 依次以第一个、第二个、第三个等等为起点去遍历字符串并且找出不连续子串的最大长度。我们可以借助哈希来解决不重复这个操作。
代码如下
class Solution
{
public:int lengthOfLongestSubstring(string s) {int ns.size();int ret 0;for(int i0;in;i){// 每次换遍历起点的时候都重新创建一个新的哈希表int hash[128]{0};for(int ji;jn;j){// 将该遍历字符插入哈希表hash[s[j]];// 如果该位置字符的次数1 则存在重复元素 直接跳出if(hash[s[j]]1)break;// 计算最大长度retmax(ret,j-i1);}}return ret;}
};
滑动窗口
暴力枚举的缺点
从我们暴力枚举画图的过程中我们能发现一个事情。如图所示 注意五角星的位置我们能发现当我们依次去使用第二个字符为起点的时候依然是遍历到了此位置那么是为什么呢
原因是我们原字符串中的a并没有移走因此我们就算以第二个字符作为起点等到遍历到第二个a的时候依然是重复的那么我们能不能遍历的时候先把重复的元素给移除掉然后再进行遍历呢
那么我们就引出了我们的滑动窗口操作。
滑动窗口步骤
我们滑动窗口分为几个简单的步骤 1.定义两个边界的变量 -- left0,right0 2.进窗口 -- 让字符进入哈希表 3.判断 -- 窗口内出现重复字符 出窗口 -- 从哈希表中删除该字符 4.更新结果 图解 代码如下
class Solution
{
public:int lengthOfLongestSubstring(string s) {int hash[128]{0};int ns.size();int ret 0 ;for(int left0,right0;rightn;right){hash[s[right]];while(hash[s[right]]1)hash[s[left]]--;retmax(right-left1,ret);}return ret;}
};
