最初的思路遍歷每個字符，找到以它開始的最長的子串。俗稱暴力法，確實很暴力，時間復(fù)雜度達到O(n^3)，唯一的好處是它能解決問題。暴力遍歷法的大概流程是準(zhǔn)備一個hash字符數(shù)組，然后遍歷每個字符放到hash表里，有重復(fù)的則記錄子串長度，然后重置hash表并從下一個字符開始。

滑動窗口解法時間復(fù)雜度可以達到O(n)，相較于暴力法節(jié)省了不少，但其思路和暴力法卻沒有根本差異，都是遍歷字符，難就難在不容易想到。暴力解法每次遇到重復(fù)的字符都會從下一個字符開始，滑動窗口則是從沖突的字符下一位開始繼續(xù)往下找，已經(jīng)確定不重復(fù)的就不用重復(fù)比較了。假定窗口存儲了最長子串，頭尾指針分別記為head, end。下一個字符指針是( end + 1)，將該字符和[ head, end ]比較，如果在位置i 出現(xiàn)相同，則記錄當(dāng)前子串長度（end - head）,將窗口指針跟新為( i + 1, end + 1)，如此比較，直到走到末尾，返回最大長度即可，確實省了很多重復(fù)計較。

//滑動窗口解法 int lengthOfLongestSubstring(char * s){int head, end, cur, len = 0, max = 0;head = end = 0;while(s[end] != '\0'){if (head != end){cur = head;while(cur < end){if (s[cur++] == s[end]){head = cur;break;}}}max = max > (end - head + 1) ? max : (end - head + 1);end++;}return max; }

=============================================================================================

Linux應(yīng)用程序、內(nèi)核、驅(qū)動、后臺開發(fā)交流討論群(745510310)，感興趣的同學(xué)可以加群討論、交流、資料查找等，前進的道路上，你不是一個人奧^_^。
?

總結(jié)

以上是生活随笔為你收集整理的面试题leetcode 3. 无重复字符的最长子串 暴力法和滑动窗口解法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。