商业网站开发实训报告,网站建设与栏目设置,建材网站建设,静态网页模板怎么用目录
力扣3. 无重复字符的最长子串
解析代码 力扣3. 无重复字符的最长子串
3. 无重复字符的最长子串 - 力扣#xff08;LeetCode#xff09;
难度 中等
给定一个字符串 s #xff0c;请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s abcabcb…目录
力扣3. 无重复字符的最长子串
解析代码 力扣3. 无重复字符的最长子串
3. 无重复字符的最长子串 - 力扣LeetCode
难度 中等
给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s abcabcbb
输出: 3
解释: 因为无重复字符的最长子串是 abc所以其长度为 3。示例 2:
输入: s bbbbb
输出: 1
解释: 因为无重复字符的最长子串是 b所以其长度为 1。
示例 3:
输入: s pwwkew
输出: 3
解释: 因为无重复字符的最长子串是 wke所以其长度为 3。 请注意你的答案必须是 子串 的长度pwke 是一个子序列不是子串。
提示
0 s.length 5 * 10^4s 由英文字母、数字、符号和空格组成
class Solution {
public:int lengthOfLongestSubstring(string s) {}
}; 解析代码 研究的对象是一段连续的区间因此继续使用「滑动窗口」思想来写。 让滑动窗口满足窗口内所有元素都是不重复的。 做法右端X元素进入窗口的时候哈希表统计这个字符的频次 如果这个字符出现的频次超过1,说明窗口内有重复元素那么就从左侧开始划出窗口, 直到X这个元素的频次变为1然后再更新结果。 如果没有超过1 说明当前窗口没有重复元素可以直接更新结果。 class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] { 0 }; // 数组模拟哈希表-s由英文字母、数字、符号和空格组成int n s.size(), ret 0, left 0, right 0;while(right n){hash[s[right]]; // 进窗口while(hash[s[right]] 1){hash[s[left]]--; // 出窗口-出到和right不在哈希表里}ret max(ret, right - left 1); // 更新结果right;}return ret;}
};
