无重复字符的最长子串
2020-04-08 16:01:08来源:博客园 阅读 ()
无重复字符的最长子串
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
起初我在进行编程的时候忽视了一点,当字符串长度为0的时候应该返回的是0而不是1,之后我还掌握了map和hash_map的区别,hash_map的底层实现方法为哈希表(时间复杂度为O(1)),而map的底层实现方式是红黑树(时间复杂度为O(log(n))),因此我起初使用map的时候会发生超时,最后本题最优的写法应该是,使用长度为256的桶进行计算,感兴趣的同学可以尝试一下。
#include <cstdio> #include <iostream> #include <cstring> #include <unordered_map> using namespace std; using namespace stdext; int lengthOfLongestSubstring(string s); int main() { string input; cin >> input; cout << lengthOfLongestSubstring(input); return 0; } int lengthOfLongestSubstring(string s) { int len = s.length(); if (len == 0) { return 0; } unordered_map<char, int> stringmap; int maxlen = 1; int begin = 0; int end = 1; while (end <= len) { if (stringmap.find(s.at(end - 1)) == stringmap.end()) { stringmap.insert(pair<char, int>(s[end - 1], end - 1)); if (stringmap.size() > maxlen) { maxlen = stringmap.size(); } end++; } else { begin = stringmap.find(s.at(end - 1))->second + 1; end = begin + 1; stringmap.clear(); } } return maxlen; }
原文链接:https://www.cnblogs.com/gxyssd/p/12660921.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- STL之set 2020-04-28
- Z 字形变换 2020-04-14
- 最长回文子串 2020-04-13
- 翻转字符串里面的单词 2020-04-10
- 用C++实现:FJ的字符串打印 2020-04-04
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash