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>来存储元素后,发现用时和空间没有继续减小,反而增大了许多,几乎与最开始采用的方法一致了。比较奇怪!

那么有没有办法消除一层循环呢?

待续......