leetcode_无重复字符的最长子串

一、题目描述

 二、思路代码

     首先有一个需要我们注意，就是其中的符号不仅仅包括字母，还包括符号，数字，空格，我在程序里面检验发现最常为95个字符。

     这个我感觉需要用滑动窗口做，即不断移动开始点和末尾点，然后不断检验。

     代码如下：

1 class Solution {
 2 public:
 3     int lengthOfLongestSubstring(string s) {
 4         //最长子串的长度
 5         int max_length=0;
 6         //如果s为空，返回0
 7         if (s=="")
 8             return max_length;
 9         //字符串s的长度
10         int length = s.size();
11         //从0位置开始搜索
12         //开始和结束位置
13         int start_loc = 0;
14         int end_loc = 0;
15         //记录两个重叠位置
16         int appear_first = -1;
17         int appear_second = 0;
18         for (int i=appear_first+1; i<length-max_length; i++)
19         {
20             if (i<appear_first+1)
21                 i = appear_first+1;
22             appear_first = i;
23             //当前开始与结束位置
24             start_loc = i;
25             end_loc = appear_second+1;
26             //只查看前95个字符
27             int j_max = min(length, i+95);
28             //判断以i为起点位置的无重复字符的子串，检验的时候j从重叠位置以后开始检验
29             for(int j=max(i+1, appear_second+1); j<j_max; j++)
30             {
31                 //appear_second设置为i+1
32                 appear_second = j;
33                 int count_num = 0;
34                 //对位置在s[j]的字符，检查其是否与前面s[start_loc:end_loc]的字符串重叠
35                 for(int k=start_loc; k<end_loc; k++)
36                 {
37                     if (s[j] != s[k])
38                         count_num++;
39                     else
40                         {
41                             //记录第一次出现位置
42                             appear_first = k;
43                             break;
44                         }
45                 }
46                 if (count_num == end_loc- start_loc)
47                     end_loc = appear_second+1;
48                 else
49                     break;
50             }
51             //更新max_length
52             max_length = max(max_length, end_loc-start_loc);
53         }
54         return max_length;
55     }
56 };      

三、参考代码

别人给出的参考代码如下（C++版本）

1 class Solution {
 2 public:
 3     int lengthOfLongestSubstring(string s) {
 4         if(s.size() == 0) return 0;
 5         unordered_set<char> lookup;
 6         int maxStr = 0;
 7         int left = 0;
 8         for(int i = 0; i < s.size(); i++){
 9             while (lookup.find(s[i]) != lookup.end()){
10                 lookup.erase(s[left]);
11                 left ++;
12             }
13             maxStr = max(maxStr,i-left+1);
14             lookup.insert(s[i]);
15     }
16         return maxStr;
17         
18     }
19 };      

纵一苇之所如，临万顷之茫然。