锐客网

  1. 首页 > it技术 > >

无重复最长字串 （C++）

题目描述：

给定一个字符串，找出不含有重复字符的最长子串的长度。
示例：
给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。
给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。
给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke" 是 子序列而不是子串。


【无重复最长字串 （C++）】加入用暴力就没什么好说的了，暴力的时间是o（o^3），用map优化的滑动窗口时间只需要O（n）；
大致思路是：用stl中的map存储记录当前无重复最长字串的字符，向后依次滑动，每遇到一个字符就判断这个字符是否在map记录中，如果有则判断这个重复的记录是否在当前无重复最长字串中，如果在就截断这个无重复最长字串，如果没有无重复最长字串的长度+1，并记录该字符。
代码如下：

#include #include #include #include #define Max(a,b) a>b?a:b using namespace std; int main() { string s; cin >> s; map mp; //键是该字符，值是字符的位置 int max = 0; int temp = 0; for(int i = 0; i < s.length(); i++) { if(mp.find(s[i]) == mp.end())//是否记录过 { mp[s[i]] = i; temp++; }else{ if(mp[s[i]] < i-temp)//重复的记录在当前的字串中 { temp++; }else{ max = Max(max,temp); temp = i - mp[s[i]]; } mp[s[i]] = i; //更新重复的字符的位置 } } cout << max << endl; return 0; }


    推荐阅读


    上一篇：php|微信支付PHP SDK的坑

    下一篇：zsh设置命令行提示符PS1