tags: String
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", 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.
Function:
public int lengthOfLongestSubstring(String s) {
// Your Code
}
題目分析
該題目是字符串類型的Medium題目，要求尋找字符串中最長的不重復(fù)子串辈双。想尋找字符串中的最長子串，肯定需要遍歷整個字符串柜砾，那么最優(yōu)化算法的時間復(fù)雜度也必須是O(n)湃望。下面介紹兩個算法：算法1是一個樸素想法的實現(xiàn)，算法效率較低痰驱；算法2是一個時間復(fù)雜度為O(n)的實現(xiàn)证芭，具有很高的算法效率和算法實現(xiàn)的可借鑒性。
算法1：自己的實現(xiàn)
public int lengthOfLongestSubstring(String s) {
int result = 0;
Queue<Character> qc = new LinkedList<>();
int sLength = s.length();
for (int i=0; i<sLength; i++) {
char ch = s.charAt(i);
if (qc.contains(ch)) {
if (result < qc.size())
result = qc.size();
while (qc.contains(ch)) { // 1. 這里不應(yīng)該用contains方法
qc.remove();
}
}
qc.add(ch);
}
if (qc.size() > result)
result = qc.size();
return result;
}
算法1的想法很樸素担映，建立一個不重復(fù)的字符串隊列废士，遍歷傳入的字符串s，如果下一個字符在當(dāng)前隊列中已存在蝇完，則判斷隊列是否是當(dāng)前最長子串官硝，然后依次移除隊頭的字符直到隊列不存在重復(fù)字符。這樣完成一次遍歷后短蜕，就可以找到最長子串氢架。下面分析一下以上實現(xiàn)的時間效率：LinkedList的contains方法是需要遍歷隊列（只要不是索引結(jié)構(gòu)，哪種數(shù)據(jù)結(jié)構(gòu)都需要遍歷）朋魔，每嘗試放入一個字符岖研，該方法都需要遍歷一次隊列，很顯然這是一個時間復(fù)雜度為O(n2)的實現(xiàn)警检。另外這份代碼中還存在一個性能問題：
- 無論是
LinkedList或ArrayList孙援，甚至是除索引結(jié)構(gòu)（如hash害淤、字典樹等）以外的數(shù)據(jù)結(jié)構(gòu)的contains方法肯定需要以某種順序遍歷數(shù)據(jù)內(nèi)容，所以能少用盡量少用拓售。
算法2：高效的算法
public int lengthOfLongestSubstring(String s) {
int lastIndices[] = new int[256]; // int數(shù)組模仿hash table
for(int i = 0; i<256; i++){
lastIndices[i] = -1;
}
char[] chArray = s.toCharArray();
int strLen = chArray.length;
int maxLen = 0;
int curLen = 0;
int start = 0; // 不重復(fù)子串起點字符的index
for(int i = 0; i<strLen; i++){
char cur = chArray[i];
if(lastIndices[cur] < start){
lastIndices[cur] = i;
curLen++;
}
else{
int lastIndex = lastIndices[cur]; // 獲取重復(fù)字符位置窥摄，更新子串起點
start = lastIndex+1;
curLen = i-start+1;
lastIndices[cur] = i;
}
if(curLen > maxLen){
maxLen = curLen;
}
}
return maxLen;
}
算法1的分析中說明了其效率低的原因，是每次加入一個字符時都需要重新遍歷隊列邻辉，確保子串的不重復(fù)性溪王。算法2針對這一點，利用hash結(jié)構(gòu)——lastIndices數(shù)組——取代了隊列的遍歷值骇，當(dāng)遍歷新的字符時莹菱，首先查看該字符是否在當(dāng)前子串中出現(xiàn)過，即lastIndices[cur] ? start吱瘩，如果沒出現(xiàn)道伟，則直接更新該字符的lastIndices信息；如果出現(xiàn)過使碾，需要同時更新start和lastIndices信息蜜徽。并在遍歷過程中更新最長子串長度。很顯然票摇，算法2的時間復(fù)雜度為O(n)拘鞋，超過Java AC的90%。
總結(jié)
該題目AC的難度不大矢门，算法1雖然效率明顯不如算法2盆色，但也是AC的。不過算法2有很值得借鑒的地方：
- 對于需要遍歷的地方祟剔，應(yīng)考慮用索引結(jié)構(gòu)（如hash）提高效率隔躲。
