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 };      

縱一葦之所如，臨萬頃之茫然。