難度: Medium
類型: Depth-First Search
=========================
找一個字串中, 最長且沒有重複字元的連續子字串長度多少。
=========================
前情題要:
=========================
思考方式:
1. 簡單就記錄目前用過的每個 char 的對應位置值為 1, 且這個 char 是 array 中第幾個 index。每次檢查新的 char 是不是在目前的 substring 出現過, 是的話, 這就是目前 substring 的最大長度, 跟目前記錄的最大長度比較, 是否要更新, 然後回到前一個相同 char 的下一個 index 再開始往後計算。
2. 這也可以用 Sliding Window 處理, 兩個 index 參數, 分別代表 sliding window 的頭尾, 沒遇到相同的 char, 頭就一直往下走。如果遇到重複的 char, 就把尾巴一直往後移動, 並更新使用過的 char 清單。我認為這個方式會比我目前附的算法更快, 但目前算法的 Runtime 已經 beat 超過一半的人了, 就有時間再更新吧!!
=========================
複雜度思考:
3_1.cpp:
Time Complexity: O( 2*N )
Space Complexity: O( 256*(sizeof(INT)+sizeof(bool) )
3_2.cpp:
Time Complexity: O( 2*N )
Space Complexity: O( 256*(sizeof(bool) )
=========================
結果:
3_1.cpp:
Runtime: 6 ms, Beats: 71.54%
Memory: 11.32 MB, Beats: 89.00%
3_2.cpp:
Runtime: 0 ms, Beats: 100%
Memory: 10.84 MB, Beats: 94.25%
