3. Longest Substring Without Repeating Characters
题面
Given a string, find the length of the longest substring without repeating characters.
给定字符串,找到最长无重复字串的长度
样例
Example 1:
Input: "abcabcbb" Output: 3 Explanation: The answer is
"abc"
, with the length of 3.
Example 2:
Input: "bbbbb" Output: 1 Explanation: The answer is
"b"
, with the length of 1.
Example 3:
Input: "pwwkew" Output: 3 Explanation: The answer is
"wke"
, with the length of 3. Note that the answer must be a substring,"pwke"
is a subsequence and not a substring.
思路
开始的思路是,蠢笨的滑动窗口
1.遍历字符串
2.以每个字符串为基准,向后搜索,暂存不重复的字符,遇到重复字符,结束内循环,统计不重复字符个数,更新结果。
时间复杂度:O(n3)
空间复杂度:> O(n)
1 class Solution { 2 public: 3 int lengthOfLongestSubstring(string s) { 4 int res = 0; 5 int len = s.length(); 6 if(len <= 1) 7 return len; 8 for(int i=0; i<len; i++) 9 { 10 string tmpStr = ""; 11 int k = i; 12 while(!find(tmpStr, s[k]) && k < len) 13 { 14 tmpStr += s[k]; 15 k++; 16 } 17 if(tmpStr.length() > res) 18 res = tmpStr.length(); 19 } 20 return res; 21 } 22 //搜索元素是否存在(已经记录过) 23 bool find(string str, char c) 24 { 25 for(int j=0; j<str.length(); j++) 26 if(str[j] == c) 27 return true; 28 return false; 29 } 30 };
优化?改进搜索复杂度
使用string find(char c)函数来替换我自己实现的find()函数,果然快了好多。
时间复杂度:大于O(n2) 小于 O(n3)
1 class Solution { 2 public: 3 int lengthOfLongestSubstring(string s) { 4 int res = 0; 5 int len = s.length(); 6 if(len <= 1) 7 return len; 8 for(int i=0; i<len; i++) 9 { 10 string tmpStr = ""; 11 int k = i;
//使用string find函数替换我的find函数 12 while(tmpStr.find(s[k]) == tmpStr.npos && k < len) 13 { 14 tmpStr += s[k]; 15 k++; 16 } 17 if(tmpStr.length() > res) 18 res = tmpStr.length(); 19 } 20 return res; 21 } 22 };
当我使用unordered_map<char, char>来存储元素后,发现用时和空间没有继续减小,反而增大了许多,几乎与最开始采用的方法一致了。比较奇怪!
那么有没有办法消除一层循环呢?
待续......