leetcode-3 最长无重复字串

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(n³)

空间复杂度：> 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(n²) 小于 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;
　　　　　　　　　//使用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>来存储元素后，发现用时和空间没有继续减小，反而增大了许多，几乎与最开始采用的方法一致了。比较奇怪！

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

待续......