Description
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.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
solution 1
根據(jù)題干，首先想到的是用set或者map來減少訪問字符（其實就是利用直接尋址來提高效率）。
我使用的是map結(jié)構(gòu)，思路是：
按字符串順序檢查每個字符是否在map中，如果存在便刪除上一個重復(fù)的字符以及其前面的字符，重新計算下一個不重復(fù)子串的長度，并且每次都比較最長長度。
show code:
public static int lengthOfLongestSubstring(String s) {
int Longest = 0;
int start = 0;
int end = 0;
int len = s.length();
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < len; i++) {
char c = s.charAt(i);
if (map.get(c) != null) {
int subEnd = map.get(c) + 1;
for (int j = start; j < subEnd; j++) {
map.remove(s.charAt(j));
}
start = subEnd;
}
map.put(c, i);
end++;
if (Longest < (end - start)) {
Longest = end - start;
}
}
return Longest;
}
時間復(fù)雜度為：，最好的情況是每個元素之訪問一次，最壞的情況是每個元素都需要訪問兩次，當(dāng)字符串的每個不重復(fù)子串的長度一致時，出現(xiàn)最壞情況。
空間復(fù)雜度為：。從代碼上看，起空間復(fù)雜度為：
，但考慮到字符集是有限的，也就是但字符串的長度比字符集大時，必定出現(xiàn)重復(fù)，此時會刪除元素。
提交代碼：
接下來嘗試進行優(yōu)化。
solution 2
既然使用了map，而眾所周知，map底層其實是利用了數(shù)組的直接尋址來實現(xiàn)的，那么我們能不能直接使用數(shù)組來實現(xiàn)呢？
這樣我們必須設(shè)計一種方法來代替hash函數(shù)的作用，來計算出字符在數(shù)組中的下標。我們知道每個字符都有對應(yīng)的數(shù)字，比如字符a是97，而且是唯一的，那么我們可以根據(jù)該特性來設(shè)計了，每個字符的大小直接對應(yīng)其在數(shù)組中的下標便可。
我們假設(shè)該字符串是都是英語的符號，而英語用128個符號編碼就夠了，也就是ASCII碼。
show code：
public int lengthOfLongestSubstring(String s) {
int[] index = new int[128];
int Longest = 0, start = 0, end = 0;
int len = s.length();
for (int i = 0; i < len; i++) {
int c = s.charAt(i);
if (index[c] != 0) {
int subEnd = index[c];
for (int j = start; j < subEnd; j++) {
index[s.charAt(j)] = 0;
}
start = subEnd;
}
index[s.charAt(i)] = i + 1;
end++;
if (Longest < (end - start)) {
Longest = end - start;
}
}
return Longest;
}
時間復(fù)雜度跟空間復(fù)雜度跟上一個解決方案是一樣的，只不過通過用數(shù)組代替map，以此來減少操作，提高效率。
提交代碼：
效率跟內(nèi)存占用都有所改善，但是依舊有優(yōu)化空間。
solution 3
如果想進一步優(yōu)化，我能想到的是進一步降低時間復(fù)雜度，把最壞情況下的2n個數(shù)組元素訪問降低為n次。如果想降低為n次，那么需要去掉方案2中重復(fù)元素的去除操作：
for (int j = start; j < subEnd; j++) {
index[s.charAt(j)] = 0;
}
基于此種思路，如果不去掉數(shù)組中的元素，那么我們就不能通過
if (index[c] != 0)
這樣來檢查元素是否存在于數(shù)組中了，必須換種思路解決問題。
在思考中，發(fā)現(xiàn)根據(jù)之前的思路，無非是用兩個指針（有別于C中的指針）來指向數(shù)組的最長不重復(fù)子串的下標，end指針一直向后遍歷，而在遇到重復(fù)時，更新start指針，判斷是否更新不重復(fù)子串的長度，然后更新字符對應(yīng)數(shù)組元素的值。
那么完全可以不用刪除重復(fù)的數(shù)組中重復(fù)的元素。如果元素不重復(fù)，那么index[c]==0，此時不更新start；如果重復(fù)，那么當(dāng)前數(shù)組index[c] - 1為已經(jīng)在數(shù)組中的重復(fù)元素的下標，那么下個子串應(yīng)該從該index[c]開始，也就是start = index[c]。而后判斷是否更新不重復(fù)子串的長度，然后更新字符對應(yīng)數(shù)組元素的值。
show code：
public int lengthOfLongestSubstring(String s) {
int[] index = new int[128];
int Longest = 0, start = 0, end = 0;
int len = s.length();
while (end < len) {
int c = s.charAt(end);
start = index[c] > start ? index[c] : start;
++end;
Longest = (end - start) > Longest ? (end - start) : Longest;
index[c] = end;
}
return Longest;
}
該算法的時間復(fù)雜度為，最多只訪問n個元素。時間復(fù)雜度沒變，依舊是
。
提交代碼：
到此，從思路上，這已經(jīng)是我所能想的極限了，當(dāng)然，到這里都是根據(jù)執(zhí)行效率進行優(yōu)化。畢竟的額外輔助空間并沒有多大（最多512字節(jié)額外內(nèi)存），當(dāng)然，如果能把int數(shù)組優(yōu)化成byte數(shù)組或者不使用額外的輔助空間，那么會占用更少的內(nèi)存空間（雖然也少不了多少）。
