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)

 class Solution {

 public:

     int lengthOfLongestSubstring(string s) {

         int res = ;

         int len = s.length();

         if(len <= )

             return len;

         for(int i=; i<len; i++)

         {

             string tmpStr = "";

             int k = i;

             while(!find(tmpStr, s[k]) && k < len)

             {

                 tmpStr += s[k];

                 k++;

             }

             if(tmpStr.length() > res)

                 res = tmpStr.length();

         }

         return res;

     }

     //搜索元素是否存在（已经记录过）

     bool find(string str, char c)

     {

         for(int j=; j<str.length(); j++)

             if(str[j] == c)

                 return true;

         return false;

     }

 };

优化？改进搜索复杂度

使用string find(char c)函数来替换我自己实现的find()函数，果然快了好多。

时间复杂度：大于O(n²) 小于 O(n³)

 class Solution {

 public:

     int lengthOfLongestSubstring(string s) {

         int res = ;

         int len = s.length();

         if(len <= )

             return len;

         for(int i=; i<len; i++)

         {

             string tmpStr = "";

             int k = i;
　　　　　　　　　//使用string find函数替换我的find函数

             while(tmpStr.find(s[k]) == tmpStr.npos && k < len)

             {

                 tmpStr += s[k];

                 k++;

             }

             if(tmpStr.length() > res)

                 res = tmpStr.length();

         }

         return res;

     }

 };

当我使用unordered_map<char, char>来存储元素后，发现用时和空间没有继续减小，反而增大了许多，几乎与最开始采用的方法一致了。比较奇怪！

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

待续......

巴特西

leetcode-3 最长无重复字串

最新文章

热门文章