leetcode（3）:Longest Substring Without Repeating Characters(defect)
摘要：
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Outp...
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.
題意簡單明瞭大致就是計算一個字串的無重複字元 的最長子字串長度（子字串即為連續的子字串）
最容易想到的實現就是兩層for迴圈遍歷，找到最大子字串，下面是筆者第一版的實現
public int lengthOfLongestSubstring(String s) {
int maxlength = 0;
for (int i = 0; i < s.length(); i++) {
Set<Character> numbers = new HashSet<>();
int times = 0;
for (int j = i; j < s.length(); j++) {
numbers.add(s.charAt(j));
times++;
int size = numbers.size();
if (size < times || size >= s.length() - i) {
if (maxlength < size) {
maxlength = size;
}
break;
}
}
}
return maxlength;
}
提交後發現：
Runtime: 54 ms, faster than 22.41% of Java online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 38.5 MB, less than 31.95% of Java online submissions for Longest Substring Without Repeating Characters.
這一版的演算法複雜度O（n^2），但是結果被leetcode大神完虐。這讓筆者意識到這道題應該有線性解或者對數解。受限於目前演算法的掌握程度還沒有學習到字串演算法哪裡，但是又不想去參考答案，所以這一版先到此告一段落。等筆者學習完字串的各種 演算法後再回過頭來重新實現，所以標題為(defect) 。