每日一道 LeetCode (46)：無重復(fù)字符的最長子串
?每天 3 分鐘，走上算法的逆襲之路。
?
前文合集
代碼倉庫
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
題目：無重復(fù)字符的最長子串
題目來源：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
給定一個字符串，請你找出其中不含有重復(fù)字符的?最長子串?的長度。
示例?1:
輸入:?"abcabcbb"
輸出:?3?
解釋:?因為無重復(fù)字符的最長子串是?"abc"，所以其長度為 3。
示例 2:
輸入:?"bbbbb"
輸出:?1
解釋:?因為無重復(fù)字符的最長子串是?"b"，所以其長度為 1。
示例 3:
輸入:?"pwwkew"
輸出:?3
解釋:?因為無重復(fù)字符的最長子串是?"wke"，所以其長度為 3。
?????請注意，你的答案必須是?子串?的長度，"pwke"?是一個子序列，不是子串。
解題方案一：暴力方案
看到這道題的第一個反應(yīng)是這題我做過??！
然后我往前一頓翻，結(jié)果嘛。。。
emmmmmmmmmmm。。。
沒找著。
既然找不著那就開始想，這題是要求一個最長無重復(fù)的子串，重點總共就兩點：
無重復(fù) 子串
最后是要求一個最長的長度，這其實就是把所有的不重復(fù)子串的長度窮舉出來，然后取最大就完事兒。
經(jīng)過上面的分析，我們成功的把這道題轉(zhuǎn)化成了一個求不重復(fù)子串的問題。
思路是滑動窗口，首先子串肯定是有長度的，即使只有 1 也是有長度的。
這時，我們指定兩個指針，一個左一個右，左右指針之間的內(nèi)容實際上就是我們的子串，長度就是我們的子串長度。
兩個指針位于初始位置時，開始移動右指針，然后每次移動以后判斷指向的元素是否和之前已有的元素有重復(fù)，如果沒有重復(fù)就一直向右移，直到有重復(fù)的為止，這就是我們的第一個子串，然后記錄這個子串的長度。
接下來左指針右移一位，然后再重復(fù)上面的過程，一直到左指針移動完整個字符串，這時我們就遍歷完成了所有的不重復(fù)的子串。
判斷子串是否用重復(fù)可以通過數(shù)據(jù)結(jié)構(gòu)來判斷，通常常用的有哈希表。
接下來就是代碼實現(xiàn)：
public?int?lengthOfLongestSubstring(String?s)?{
????Set?setChars?=?new?HashSet<>();
????int?length?=?s.length();
????//?定義右指針
????int?right?=?-1;
????//?定義返回結(jié)果
????int?result?=?0;
????for?(int?i?=?0;?i?????????if?(i?!=?0)?{
????????????//?左指針右移一次，刪掉前一個字符
????????????setChars.remove(s.charAt(i?-?1));
????????}
????????while?(right?+?1?1)))?{
????????????//?移動右指針，像?set?中添加字符
????????????setChars.add(s.charAt(right?+?1));
????????????++right;
????????}
????????result?=?Math.max(result,?right?-?i?+?1);
????}
????return?result;
}
解題方案二：優(yōu)化后
上面這個方案有個缺陷，就是每次左指針只是單純的 + 1 ，實際上左指針可以直接移動到右指針 + 1 的位置，因為當(dāng)前的子串已經(jīng)有重復(fù)了，直接跳過就好了。
public?int?lengthOfLongestSubstring_1(String?s)?{
????int?length?=?s.length(),?result?=?0;
????Map?map?=?new?HashMap<>();
????for?(int?left?=?0,?right?=?0;?right?????????//?如果含有右指針指向的元素，則移動左指針
????????if?(map.containsKey(s.charAt(right)))?{
????????????left?=?Math.max(map.get(s.charAt(right)),?left);
????????}
????????result?=?Math.max(result,?right?-?left?+?1);
????????map.put(s.charAt(right),?right?+?1);
????}
????return?result;
}
解題方案三：極致優(yōu)化
上面的方案還有沒有優(yōu)化空間，當(dāng)然有，我們對循環(huán)次數(shù)已經(jīng)沒辦法優(yōu)化了，那么還能優(yōu)化的就剩下了判斷當(dāng)前字符是否存在。
比哈希表尋址還要快的可能有什么？當(dāng)然是直接操作數(shù)組咯~~~
首先可以定義一個 128 位的數(shù)組，然后我們通過數(shù)組進(jìn)行判斷當(dāng)前字符是否存在：
public?int?lengthOfLongestSubstring_2(String?s)?{
????int?n?=?s.length();
????int?result?=?0;
????int[]?charIndex?=?new?int[128];
????for?(int?left?=?0,?right?=?0;?right?????????char?c?=?s.charAt(right);
????????left?=?Math.max(charIndex[c],?left);
????????result?=?Math.max(result,?right?-?left?+?1);
????????charIndex[c]?=?right?+?1;
????}
????return?result;
}
