資訊專欄INFORMATION COLUMN
摘要：解題思路本題借助實(shí)現(xiàn)。如果字符未出現(xiàn)過(guò)，則字符，如果字符出現(xiàn)過(guò)，則維護(hù)上次出現(xiàn)的遍歷的起始點(diǎn)。注意點(diǎn)每次都要更新字符的位置最后返回時(shí)，一定要考慮到從到字符串末尾都沒(méi)有遇到重復(fù)字符的情況，所欲需要比較下和的大小。
Longest Substring Without Repeating Characters
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.
1.解題思路
本題借助HashMap實(shí)現(xiàn)。
1） 如果字符未出現(xiàn)過(guò)，則put(字符，index);
2) 如果字符出現(xiàn)過(guò)，則維護(hù)len=上次出現(xiàn)的index-遍歷的起始點(diǎn)。
那問(wèn)題就到了如何去定義遍歷的起始點(diǎn)呢，我們當(dāng)然可以從0開(kāi)始，然后每次加1，但是通過(guò)下面的例子，我們很容易就發(fā)現(xiàn)這樣會(huì)有很多情況冗余：
“abcdecf”
我們從index 0開(kāi)始，到第二個(gè)字符c-index5，我們會(huì)發(fā)現(xiàn)已經(jīng)存在，所以len,5-0=5；但如果我們之后index從1開(kāi)始，我們會(huì)發(fā)現(xiàn)必然還會(huì)在index5這邊停止，為了減少這種冗余，我們想到可以在一次重復(fù)后，將start置為重復(fù)元素Index+1，這里就是index3-d, 這樣我們?cè)谂龅揭呀?jīng)存在的字符時(shí)，就要再加上一個(gè)判斷，看其上一次出現(xiàn)是否在start之前，如果在start之前，則不作考慮，直接Put進(jìn)新的位置；如果是在start之后，則就表明確實(shí)遇到了重復(fù)點(diǎn)。
注意點(diǎn)：
1）每次都要更新字符的位置；
2）最后返回時(shí)，一定要考慮到從start到s.length(字符串末尾)都沒(méi)有遇到重復(fù)字符的情況，所欲需要比較下maxLen和s.length()-start的大小。
2.代碼
public class Solution {
public int lengthOfLongestSubstring(String s) {
if(s.length()==0) return 0;
HashMap hm=new HashMap();
int start=0;
int maxLen=1;
for(int i=0;i=start){
int len=i-start;
maxLen=Math.max(maxLen,len);
start=hm.get(s.charAt(i))+1;
}
hm.put(s.charAt(i),i);
}
return Math.max(maxLen,s.length()-start);
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/69801.html
摘要：原問(wèn)題我的沙雕解法無(wú)重復(fù)字母存在重復(fù)字母挨打最暴力的無(wú)腦解法，耗時(shí)。。。 原問(wèn)題 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)記為，并用無(wú)重復(fù)字符計(jì)數(shù)器記錄無(wú)重復(fù)字符的長(zhǎng)度，再在更新其最大值。循環(huán)完整個(gè)字符串后，返回最大值。 Problem Given a string, find the length of the longest substring without repeating characters. Examples: Given ...
摘要：題目詳情題目要求輸入一個(gè)字符串，我們要找出其中不含重復(fù)字符的最長(zhǎng)子字符串，返回這個(gè)最長(zhǎng)子字符串的長(zhǎng)度。對(duì)于字符串中的每一個(gè)字符，先判斷中是否已經(jīng)存在這個(gè)字符，如果不存在，直接將添加到，如果已存在，則新的字符串就從不含前一個(gè)字符的地方開(kāi)始。 題目詳情 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 ...
Problem 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...
閱讀 2305·2021-09-30 09:47
閱讀 2223·2021-09-26 09:55
閱讀 2954·2021-09-24 10:27
閱讀 1543·2019-08-27 10:54
閱讀 971·2019-08-26 13:40
閱讀 2499·2019-08-26 13:24
閱讀 2423·2019-08-26 13:22
閱讀 1735·2019-08-23 18:38
