江苏品牌网站设计,网站开发产生费用分录怎么写,网络规划设计师可以挂证吗,wordpress 数据库账号个人主页#xff1a;兜里有颗棉花糖 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 #x1f354;本专栏旨在提高自己算法能力的同时#xff0c;记录一下自己的学习过程#xff0c;希望… 个人主页兜里有颗棉花糖 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 本专栏旨在提高自己算法能力的同时记录一下自己的学习过程希望对大家有所帮助 希望我们一起努力、成长共同进步。 原题链接点击直接跳转到该题目 目录 1️⃣题目描述2️⃣算法分析3️⃣代码编写 1️⃣题目描述
给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。
示例1 输入: s “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”所以其长度为 3。 示例2 输入: s “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”所以其长度为 1。 示例3 输入: s “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”所以其长度为 3。 请注意你的答案必须是 子串 的长度“pwke” 是一个子序列不是子串。 提示
0 s.length 5 * 1 0 4 10^{4} 104s 由英文字母、数字、符号和空格组成
2️⃣算法分析
遍历字符串 s右边界 right 从 0 开始逐步向右移动 每次将右边界对应的字符出现次数加 1即 hash[s[right]]表示进窗口。 判断 hash[s[right]] 是否大于 1如果是说明该字符重复了需要将窗口的左边界向右移动直到窗口中不包含重复字符同时更新 hash 数组中左边界字符出现次数的计数。 更新 ret 的值即 ret max(ret,right - left 1)。
返回 ret即为无重复字符的最长子串的长度。
3️⃣代码编写
class Solution {
public:int lengthOfLongestSubstring(string s) {int n s.size();int hash[128] { 0 };int left 0,right 0,ret 0;for(left 0,right 0;right n;right){hash[s[right]]; // 进窗口while(hash[s[right]] 1) hash[s[left]]--; // 出窗口ret max(ret,right - left 1);}return ret;}
};最后就顺利通过啦!
