品牌型网站建设哪里好,南通seo快速排名,wordpress主题价格,wordpress本地批量传文章文章目录滑动窗口算法1 涉及知识点 #xff1a;unordered_set 容器2 参数详情3 例题滑动窗口算法
滑动的窗口#xff0c;每次记录下窗口的状态#xff0c;再找出符合条件的窗口使用滑动窗口减少时间复杂度
1 涉及知识点 #xff1a;unordered_set 容器
说明#xff1a;…
文章目录滑动窗口算法1 涉及知识点 unordered_set 容器2 参数详情3 例题滑动窗口算法
滑动的窗口每次记录下窗口的状态再找出符合条件的窗口使用滑动窗口减少时间复杂度
1 涉及知识点 unordered_set 容器
说明unordered_set容器与set的区别就是set容器会自行对存储的数据排序而 unordered_set 容器不会。
不再以键值的形式存储数据而是直接存储数据的值容器内部存储的各个元素的值都不相等且不能被修改不会对容器内部的元素进行排序
2 参数详情
unordered_setint lookup;//构造函数
lookup.find(s[i]) //查询元素是否在结合内
lookup.end() //end()函数是最后一个元素的下一个位置
lookup.erase(s[left]);//删除元素
lookup.insert(s[i]) //插入元素3 例题
题目描述无重复字符的最长子串
输入: s abcabcbb
输出: 3
解释: 因为无重复字符的最长子串是 abc所以其长度为 3。
输入: s pwwkew
输出: 3
解释: 因为无重复字符的最长子串是 wke所以其长度为 3。请注意你的答案必须是 子串 的长度pwke 是一个子序列不是子串。解题思路 利用滑动窗口的思想也就是定义一个lookup窗口让窗口一步一步滑动遍历输入的字符串。划过的字符与刚刚输入的字符比较若是不相等继续滑动滑出来的长度就是不含有重复字符的最长字串的长度。若是相等就是下次再比较就从相等的字符的下一个字符开始。 注意若是空字符串直接返回0
参考代码c
class Solution {
public:int lengthOfLongestSubstring(string s) {if (s.size()0)return 0;int maxlong0;int left0;unordered_set int lookup;for(int i0;is.size();i){while(lookup.find(s[i])!lookup.end()){lookup.erase(s[left]);left;}lookup.insert(s[i]);maxlongmax(maxlong,i-left1);}return maxlong;}
};
