ppt模板在哪里找_徐州模板建站系统_宁波企业seo服务_杭州小周seo

滑动窗口思想

题目

题目链接
3. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

我的思路
滑动窗口+哈希
哈希使用的map

class Solution {
public:int lengthOfLongestSubstring(string s) {int n=s.size();int right=0;int left=0;int sum=0;int maxlen=0;map<char,int> mp;while(right<n){while(mp.count(s[right])==0&&right<n){mp[s[right]]++;sum++;right++;}maxlen=max(maxlen,sum);sum--;mp.erase(s[left]);left++;// right++;  这里right不应该++}return maxlen;}
};

bug点:

1. while循环内没有判断right<n，则最后两个字符没办法判断
2. 什么时候right++？当左边界left增加时,即滑动窗口缩小时，right不变；right只在满足题目条件时增加
3. 注意maxlen的最大值不是INT_MAX，而是0

冗余
4. 哈希表如何构造？使用map只使用了map的“唯一”关键字的性质，后面的int没有用到； sum的设置冗余可以换成 max(maxlen, right-left)
5. 左指针并不需要依次递增，即多了很多无谓的循环。 发现有重复字符时，可以直接把左指针移动到第一个重复字符的下一个位置即可。

精进
看的官方题解评论区，发现，每次left可以直接从下一个相同字符的下一个开始，使用map<char,int> int 记录每个字符的位置，出现相同字符则记录的是该字符出现的上一个位置，如abcdefdgh, 当遇到第二个d时left会跳到e, 因为在a-第一个d之间的连续字串的长度都比a-d小，所以这是不必要的循环，直接跳到第一个d的下一个。
abcdefagh 遇到第二个a时会跳到b

class Solution {
public:int lengthOfLongestSubstring(string s) {int n=s.size();int left=0;int maxlen=0;map<char,int> mp;for(int right=0;right<n;right++){char ch=s.at(right);  //这里没有插入呢！只是记录当前right的位置if(mp.count(ch)==1){left=max(mp[ch]+1,left); //这里max里的left记录的是上一个相同字符的位置的下一个，上一次的下一个位置，和当前的下一个位置相比较//left=right+1;  这个是当前的=相同位置的下一个//left=mp[ch]+1;   这个是上一个的下一个} maxlen=max(maxlen,right-left+1);  //不好的地方是每次都要计算一下maxlen，而不是在滑动窗口停止时计算mp[ch]=right;     //更新相同的关键字的位置，覆盖}return maxlen;}
};

官方题解：

class Solution {
public:int lengthOfLongestSubstring(string s) {// 哈希集合，记录每个字符是否出现过unordered_set<char> occ;int n = s.size();// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动int rk = -1, ans = 0;// 枚举左指针的位置，初始值隐性地表示为 -1for (int i = 0; i < n; ++i) {if (i != 0) {// 左指针向右移动一格，移除一个字符occ.erase(s[i - 1]);}while (rk + 1 < n && !occ.count(s[rk + 1])) {// 不断地移动右指针occ.insert(s[rk + 1]);++rk;}// 第 i 到 rk 个字符是一个极长的无重复字符子串ans = max(ans, rk - i + 1);}return ans;}
};作者：LeetCode-Solution
链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

知识点补充
一、map的使用

1. 定义：

map<int ,string> mp;

2. 赋值插入

mp.insert(pair<int, string>(1,"first"));```
mp.insert(map<int,string>::value_type(2,"second"));
mp[1]="third";

3. 查找
   count看是否找到该关键字；
   find定位元素出现的位置，返回的时迭代器，出现时返回该位置的迭代器；没有找到，返回迭代器等于end函数返回的迭代器。

map<string,int>mp1,::iterator it;
if(mp1.count("first")==0){cout<<"not find";}//没找到该关键字，=1找到该关键字
it=mp1.find("first");
if(mp1!=mp.end()){cout<<"find success"<<it->second;}
else {cout<<"not find";}

4. 删除

mp.erase("first");   //用关键字删除
mp.erase(mp.begin(),mp.end()) ;   //成片删除， 删除区间：前闭后开

5. 排序
   map种元素自动按照key升序排序（从小到大）；

二、unordered_set用法
unordered_set是一种关联容器，unordered_set和unordered_map是基于hashtable，是无序的。set和map内部实现是基于RB-Tree，是有序的，

1. 定义

unordered_set<int> hash;

2. 操作
   size() 元素个数
   empty()
   maxsize() 获取最大容量值
   find(“ggg”) 通过给定主键查找元素
   insert(“aaa”)
   erase(“aaa”)
   clear() 清空
   swap() //hash.swap(hash2)