Last Updated on 2021-05-11 by Clay
題目
Given a string s, find the length of the longest substring without repeating characters.Example:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.這是個非常單純的題目：輸入是唯一字串，我們要在其中找到字元不重複的子字串。
解題思路
我自己的第一感是建立個陣列/佇列/字串，在遍歷整個輸入字串，只要當前判斷的字元不存在於建立的陣列中，即將該字元加入此陣列；如果這個字元已經存在陣列中，則一直刪除陣列開頭的值，直到當前判斷的字元不存在於陣列中為止。
這個說來可能有些攏統，以下直接看看程式碼：
C++ 程式碼
class Solution { public: int lengthOfLongestSubstring(string s) { int max_len = 0; deque<char> sub_str = {}; for (int i=0; i<s.size(); i++) { while (find(sub_str.begin(), sub_str.end(), s[i]) != sub_str.end()) { sub_str.pop_front(); } sub_str.push_back(s[i]); if (sub_str.size() > max_len) { max_len = sub_str.size(); } } return max_len; } };
Python 程式碼
class Solution(object): def lengthOfLongestSubstring(self, s): sub_str = '' max_len = 0 for w in s: while w in sub_str: sub_str = sub_str[1:] else: sub_str += w max_len = max(len(sub_str), max_len) return max_lenㄙㄟ
其中很有趣的是，Python 在切割時使用字串切割比陣列更快，我還是第一次知道這種事情。