Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

最长无重复子串问题 leetcode 3

谋莽台 2019-12-30 00:18:00 阅读数:43 评论数:0 点赞数:0 收藏数:0

一.代码及注释

class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.size(); //字符串的长度
int ans = ; //最长无重复子串的长度
//建立map表 key为字符 val为该字符的下一个坐标位置
//val取符号坐标+1用于更新start
unordered_map<char,int> m;
//定义start和end end即为当前字符,不断+1
for(int start=,end=;end<n;end++){
//当前字符为c
char c = s[end];
//如果map中有当前字符(即出现了重复的字符),则进入if语句
if(m.find(c)!=m.end()){
/*
两种情况:
1.如果start比m[c]小,如pwwkew,start为2,end为5两个w相等
则start就更新为3,以end为结尾的最长无重复子串才能是5-3+1=3;
2.如果start比m[c]大,如kwawk,如图所示,start为2,end为5,需要
start保持不变
*/
start = max(m[c],start);
}
//ans更新,end-start+1即以当前end为结尾的最长无重复串
ans = max(ans,end-start+);
//添加数据
 m.erase(c);
m.insert(make_pair(c,end+));
}
return ans;
}
};

二.图解

 

三.需要map的知识点(常用总结)

map的插入:常常需要和删除配合使用

map.erase(key);

map.insert(make_pair(key,val));

map的访问:直接通过访问下标

m[下标];

map的循环

auto iter = m.begin();

while(iter!=m.end()){

cout<<iter.first()<<endl;  //输出key

cout<<iter.second()<<endl;//输出val

}

map的查找

m.find(key);返回的是迭代器,可用m.find(key)!=m.end()判断是否存在该key。

m.count(key);返回迭代器的数量,用于可重复的map。

版权声明
本文为[谋莽台]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/moumangtai/p/12117247.html