不夠優秀，發量尚多，千錘百鍊，方可成佛。
算法的重要性不言而喻，無論你是研究者，還是最近比較火熱的IT 打工人，都理應需要一定的算法能力，這也是面試的必備環節，算法功底的展示往往能讓面試官眼前一亮，這也是在大多數競爭者中脫穎而出的重要影響因素。
然而往往大多數人比較注重自身的實操能力，著重於對功能的實現，卻忽視了對算法能力的提高。有的時候採用不同的算法來解決同一個問題，運行效率相差還是挺大的，畢竟我們最終還是需要站在客戶的角度思考問題嘛，能給用戶帶來更加極致的體驗當然再好不過了。
萬法皆空，因果不空。Taoye之前也不怎麼情願花費太多的時間放在算法上，算法功底也是相當的薄弱。這不，進入到了一個新的學習階段，面對導師的各種「嚴刑拷打」和與身邊人的對比，才開始意識到自己「菜」的事實。
講到這，我的眼角又溼了！！！
這次的題目是LeeTCode 熱題 HOT 100的第三題，難度屬於中等，感覺比第二題稍微簡單點。
下面，我們就來看看這道題吧。
題目：無重複字符的最長子串給定一個字符串，請你找出其中不含有重複字符的 最長子串 的長度。
題目Url：https://leetcode.com/problems/longest-substring-without-repeating-characters/
示例輸入: "abcabcbb"
輸出: 3
解釋: 因為無重複字符的最長子串是 "abc"，所以其長度為 3。
輸入: "bbbbb"
輸出: 1
解釋: 因為無重複字符的最長子串是 "b"，所以其長度為 1。
輸入: "pwwkew"
輸出: 3
解釋: 因為無重複字符的最長子串是 "wke"，所以其長度為 3。請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串。
根據題目的要求，我們需要輸出無重複字符的最長子串長度，我們不妨用result來代替。
由於需要記錄輸入字符串的每個字符在之前遍歷的子串中是否重複，所以我們需要一個容器對已經遍歷過的字符進行臨時存儲。
進過分析，我們可以發現，臨時容器存儲的數據主要有兩個，一個是字符值，還有一個就是字符在輸入字符串中的索引值，且這兩個屬性有個一一映射關係。所以我們不難得到，可以通過創建一個HashTable來代替該容器，在Python中，則可以使用dict字典來表示。（與HOT 100第一題意思類似）我們不妨將該臨時字典容器用temp_dict來表示。
此外，在對輸入字符串進行遍歷的過程中，還需要用到一個臨時索引，主要用來記錄與遍歷當前字符值相同的上一個字符的索引，比如：示例1中輸入字符串為「abcabcbb」，當我們遍歷到索引為3的時候，此時字符為a，而上一個字符a的索引為0。所以，當我們遍歷到的字符在temp_dict中出現過時，則需要更改與該字符相同的上一個字符的索引，也就是由初始值-1更改為0。我們不妨將這個臨時索引用temp_index來表示
至此，我們得到的完整算法如下（推敲算法流程和下面代碼的實現）：
初始化三個變量：result, temp_dict, temp_index = 0, dict(), -1，目標返回值result和temp_dict初始為0和dict()不用解釋，而temp_index之所以初始為-1，主要是因為我們返回新的result的時候，需要與之前的result和遍歷至此時候的最大長度進行比較，取二者的最大值。
對輸入的字符串進行遍歷，判斷如果當前遍歷字符在temp_dict中，且該字符上次出現的索引大於當前更新前的temp_index臨時索引，則需要更新臨時索引temp_index和臨時字典temp_dict。否則將首次出現的字符添加到臨時字典temp_index中，並更新result的值。
遍歷完輸入的字符串之後，返回result
該算法的Python實現：
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
result, temp_dict, temp_index = 0, dict(), -1 # 定義初始變量
for index, value in enumerate(s): # 對輸入字符串s進行循環遍歷
if value in temp_dict and temp_dict[value] > temp_index: # 判斷temp_dict是更新還是添加
temp_index, temp_dict[value] = temp_dict[value], index # 更新temp_dcit和temp_index
# 添加temp_dict，並修改result
else: temp_dict[value], result = index, max(result, index - temp_index)
return result # 遍歷完成返回目標結果
該算法的C++實現（實現思想同Python）：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int result = 0, temp_index = -1;
unordered_map<char, int> temp_dict;
for (int index = 0; index < s.size(); index++) {
if (temp_dict.count(s[index]) != 0) {
if (temp_dict[s[index]] > temp_index) {
temp_index = temp_dict[s[index]];
temp_dict[s[index]] = index;
}
}else {
temp_dict[s[index]] = index;
result = result > (index - temp_index) ? result : (index - temp_index);
}
}
return result;
}
};
另外，官方給出了一種滑動窗口的方式實現，主要是找出從每一個字符開始，不包含重複字符的最長子串。
滑動窗口的主要核心思想可以參考官方，或者下面三篇講解的思路，感覺講的很不錯：
《LeetCode第三題：解題思路》: https://blog.csdn.net/boling_cavalry/article/details/86563586
《LeetCode第三題：編碼實現》：https://blog.csdn.net/boling_cavalry/article/details/86654969
《LeetCode第三題：兩次優化》：https://blog.csdn.net/boling_cavalry/article/details/86655675
推薦閱讀：
LeetCode 熱題 HOT 100（00，兩數之和）
LeetCode 熱題 HOT 100（01，兩數相加）
Taoye滲透到一家黑平臺總部，背後的真相細思極恐
《大話資料庫》-SQL語句執行時，底層究竟做了什麼小動作？
那些年，我們玩過的Git，真香
基於Ubuntu+Python+Tensorflow+Jupyter notebook搭建深度學習環境
網絡爬蟲之頁面花式解析
手握手帶你了解Docker容器技術
一文詳解Hexo+Github小白建站
打開ElasticSearch、kibana、logstash的正確方式