宁波市奉化区建设局网站镇网站制作价格

滑动窗口算法

• 滑动的窗口，每次记录下窗口的状态，再找出符合条件的窗口
• 使用滑动窗口减少时间复杂度

1 涉及知识点 ：unordered_set 容器

说明：unordered_set容器与set的区别就是set容器会自行对存储的数据排序，而 unordered_set 容器不会。

• 不再以键值的形式存储数据，而是直接存储数据的值
• 容器内部存储的各个元素的值都不相等，且不能被修改
• 不会对容器内部的元素进行排序

2 参数详情

unordered_set<int> 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 maxlong=0;int left=0;unordered_set <int> lookup;for(int i=0;i<s.size();i++){while(lookup.find(s[i])!=lookup.end()){lookup.erase(s[left]);left++;}lookup.insert(s[i]);maxlong=max(maxlong,i-left+1);}return maxlong;}
};