資訊專欄INFORMATION COLUMN
摘要：題目解析題目含義很簡單，即求出沒有字符重復(fù)的子字符串的長度。例如很明顯就是個(gè)由完全重復(fù)字符組成的字符串，所以它的答案長度為。所以綜合來看該算法的效率為。
題目
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.
題目含義很簡單，即求出沒有字符重復(fù)的子字符串的長度。例如bbbbb很明顯就是個(gè)由完全重復(fù)字符組成的字符串，所以它的答案長度為1。
解法1 : 遍歷字符串構(gòu)成無重復(fù)字符字符串最簡單的方法就是通過遍歷字符串的每一個(gè)字符，循環(huán)的構(gòu)造子字符串，遇到重復(fù)字符便停止，然后得出最長長度的那個(gè)字符串。
public static int lengthOfLongestSubstring(String s) {
int maxLength = 0;
for(int index = 0 ; index=0){
if(temp.length()>maxLength)
maxLength = temp.length();
break;
}else{
temp.append(s.charAt(buffer));
}
}
// 如果該子串的長度大于當(dāng)前最大長度，那么替換為最長長度
if(temp.length()>maxLength){
maxLength = temp.length();
}
}
return maxLength;
}
這個(gè)方法非常好理解，但是唯一的問題就是效率非常低,在外層有兩層循環(huán)，在尋找字符操作時(shí)(temp.indexOf(currStr))也要循環(huán)一遍，所以該算法的復(fù)雜度為O(n^3)
解法2 滑動(dòng)構(gòu)造子串 public static int lengthOfLongestSubstring(String s){
// 非空校驗(yàn)
if(s==null || s.isEmpty()){
return 0;
}
int length = s.length();
// 定義滑動(dòng)標(biāo)志位:indexOne，indexTwo s[indexOne]~s[indexTwo]之間的字符串組成一個(gè)不重復(fù)字符的子
// 串
int indexOne = 0 , indexTwo = 0;
int maxLength = 0;
Set set = new HashSet<>();
while(indexOne < length && indexTwo < length){
// 如果set不包含新字符
if(!set.contains(s.charAt(indexTwo))){
// 那么indexTwo++ ，同時(shí)將新字符添加到set中
set.add(s.charAt(indexTwo++));
// 當(dāng)前子串長度為 indexTwo - indexOne
maxLength = Math.max(maxLength , indexTwo - indexOne);
}else{
set.remove(s.charAt(indexOne++));
}
}
return maxLength;
}
滑動(dòng)構(gòu)造子串的意思即通過兩個(gè)索引indexOne，indexTwo動(dòng)態(tài)構(gòu)造子串，如果下一個(gè)字符沒重復(fù)，那么indexTwo+1，如果下一個(gè)字符已重復(fù)，那么indexOne+1。
在最好的情況下，例如輸入"abcde"的時(shí)候，下一個(gè)字符一直是新的字符，那么indexTwo可以一直+1，直到字符串被遍歷完，這時(shí)候的效率為O(n)。
在最差的情況下，例如輸入"bbbbb"的時(shí)候，下一個(gè)字符一直是重復(fù)字符，那么程序一直執(zhí)行indexTwo+1后indexOne+1的循環(huán)，也即indexOne和indexTwo分別遍歷了一遍了字符串，那么這時(shí)候的效率為O(2n)。
所以綜合來看該算法的效率為O(n)。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/72391.html
摘要：解題思路本題借助實(shí)現(xiàn)。如果字符未出現(xiàn)過，則字符，如果字符出現(xiàn)過，則維護(hù)上次出現(xiàn)的遍歷的起始點(diǎn)。注意點(diǎn)每次都要更新字符的位置最后返回時(shí)，一定要考慮到從到字符串末尾都沒有遇到重復(fù)字符的情況，所欲需要比較下和的大小。 Longest Substring Without Repeating CharactersGiven a string, find the length of the lon...
摘要：原問題我的沙雕解法無重復(fù)字母存在重復(fù)字母挨打最暴力的無腦解法，耗時(shí)。。。 原問題 Given a string, find the length of the?longest substring?without repeating characters. Example 1: Input: abcabcbb Output: 3 Explanation: The answer is a...
摘要：建立數(shù)組，存儲(chǔ)個(gè)字符最近一次出現(xiàn)的位置。首次出現(xiàn)某字符時(shí)，其位置標(biāo)記為，并用無重復(fù)字符計(jì)數(shù)器記錄無重復(fù)字符的長度，再在更新其最大值。循環(huán)完整個(gè)字符串后，返回最大值。 Problem Given a string, find the length of the longest substring without repeating characters. Examples: Given ...
摘要：題目詳情題目要求輸入一個(gè)字符串，我們要找出其中不含重復(fù)字符的最長子字符串，返回這個(gè)最長子字符串的長度。對(duì)于字符串中的每一個(gè)字符，先判斷中是否已經(jīng)存在這個(gè)字符，如果不存在，直接將添加到，如果已存在，則新的字符串就從不含前一個(gè)字符的地方開始。 題目詳情 Given a string, find the length of the longest substring without repe...
摘要：哈希表是最自然的想法。在遍歷字符串時(shí)，我們先根據(jù)哈希表找出該字符上次出現(xiàn)的位置，如果大于等于子字符串首，便更新子字符串首。結(jié)束后，將該字符新的位置放入哈希表中。 Longest Substring Without Repeating Characters 最新更新解法：https://yanjia.me/zh/2018/12/... Given a string, find the ...
閱讀 1017·2021-11-16 11:45
閱讀 2194·2021-10-09 09:44
閱讀 1415·2019-08-30 14:03
閱讀 1219·2019-08-26 18:28
閱讀 3391·2019-08-26 13:50
閱讀 1794·2019-08-23 18:38
閱讀 3507·2019-08-23 18:22
閱讀 3673·2019-08-23 15:27
