無(wú)重復(fù)字符的最長(zhǎng)子串(LeetCode--3.無(wú)重復(fù)字符的最長(zhǎng)子串)

題目描述

找出一個(gè)字符串中不含有重復(fù)字符的最長(zhǎng)子串的長(zhǎng)度挤聘。

示例:
輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "abc"侨舆,所以其長(zhǎng)度為 3谈息。
輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "b",所以其長(zhǎng)度為 1巨双。

解析

算法技巧:

應(yīng)用HashMap存儲(chǔ)遍歷的字符及其坐標(biāo)索引噪猾,以減少遍歷字符串次數(shù),利用空間換取時(shí)間

實(shí)現(xiàn)方法:

方法一:暴力法依次遍歷字符串中每個(gè)字符作為開(kāi)頭的最長(zhǎng)子串筑累,在眾多子串中選出最長(zhǎng)子串袱蜡。
方法二:在方法一基礎(chǔ)上每次查找新的字符開(kāi)頭的子串時(shí),記錄已經(jīng)存在的字符慢宗,這樣可以消除為判斷是否重復(fù)而往回校驗(yàn)的時(shí)間消耗坪蚁。
方法三:遍歷一趟字符串,并且不走回頭路镜沽。需要記錄子串開(kāi)始的位置head敏晤,和HashMap記錄已經(jīng)存在的字符,如果遇到當(dāng)前字符已經(jīng)存在則統(tǒng)計(jì)當(dāng)前的最長(zhǎng)子串缅茉,head不需要移動(dòng)到1嘴脾,而是移動(dòng)到重復(fù)字符的后一位。例如蔬墩,s[j]在s[i]~s[j-1]存在译打,下標(biāo)為k(i <= k <= j-1 ),則新的子串從k + 1開(kāi)始即可拇颅,因?yàn)閕與k之間開(kāi)頭的字符不可能存在長(zhǎng)度超過(guò)j-i的不重復(fù)子串奏司。同時(shí),考慮一種特殊情況樟插,如果HashMap中存在當(dāng)前字符韵洋,但是當(dāng)前字符卻不在遍歷的區(qū)間,那么此時(shí)head不需要移動(dòng)黄锤,但是要更新HashMap麻献。

代碼
public int lengthOfLongestSubstring(String s) {
    int head = 0, tail = head, longest = 0;
    Map<Character, Integer> map = new HashMap<>();
    while(tail < s.length()){
        char c = s.charAt(tail);
        Integer i = map.get(c);
        if(i != null){//HashMap存在當(dāng)前字符c
            longest = (tail - head) > longest ? (tail - head) : longest;//遇到重復(fù)時(shí)更新最長(zhǎng)子串長(zhǎng)度
            head = head > i ? head : i + 1;//判斷是否在當(dāng)前區(qū)間內(nèi),決定是否改變head
        }
        map.put(c, tail);//新插入或者更新HashMap
        tail++;
    }
    return (tail - head) > longest ? (tail - head) : longest;
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末猜扮,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子监婶,更是在濱河造成了極大的恐慌旅赢,老刑警劉巖齿桃,帶你破解...
    沈念sama閱讀 218,941評(píng)論 6 508
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異煮盼,居然都是意外死亡短纵,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,397評(píng)論 3 395
  • 文/潘曉璐 我一進(jìn)店門(mén)僵控,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)香到,“玉大人,你說(shuō)我怎么就攤上這事报破∮凭停” “怎么了?”我有些...
    開(kāi)封第一講書(shū)人閱讀 165,345評(píng)論 0 356
  • 文/不壞的土叔 我叫張陵充易,是天一觀的道長(zhǎng)梗脾。 經(jīng)常有香客問(wèn)我,道長(zhǎng)盹靴,這世上最難降的妖魔是什么炸茧? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 58,851評(píng)論 1 295
  • 正文 為了忘掉前任,我火速辦了婚禮稿静,結(jié)果婚禮上梭冠,老公的妹妹穿的比我還像新娘。我一直安慰自己改备,他們只是感情好控漠,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,868評(píng)論 6 392
  • 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著绍妨,像睡著了一般润脸。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上他去,一...
    開(kāi)封第一講書(shū)人閱讀 51,688評(píng)論 1 305
  • 那天毙驯,我揣著相機(jī)與錄音,去河邊找鬼灾测。 笑死爆价,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的媳搪。 我是一名探鬼主播铭段,決...
    沈念sama閱讀 40,414評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼秦爆!你這毒婦竟也來(lái)了序愚?” 一聲冷哼從身側(cè)響起,我...
    開(kāi)封第一講書(shū)人閱讀 39,319評(píng)論 0 276
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤等限,失蹤者是張志新(化名)和其女友劉穎爸吮,沒(méi)想到半個(gè)月后芬膝,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,775評(píng)論 1 315
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡形娇,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,945評(píng)論 3 336
  • 正文 我和宋清朗相戀三年锰霜,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片桐早。...
    茶點(diǎn)故事閱讀 40,096評(píng)論 1 350
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡癣缅,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出哄酝,到底是詐尸還是另有隱情友存,我是刑警寧澤,帶...
    沈念sama閱讀 35,789評(píng)論 5 346
  • 正文 年R本政府宣布炫七,位于F島的核電站爬立,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏万哪。R本人自食惡果不足惜侠驯,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,437評(píng)論 3 331
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望奕巍。 院中可真熱鬧吟策,春花似錦、人聲如沸的止。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 31,993評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)诅福。三九已至匾委,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間氓润,已是汗流浹背赂乐。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,107評(píng)論 1 271
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留咖气,地道東北人挨措。 一個(gè)月前我還...
    沈念sama閱讀 48,308評(píng)論 3 372
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像崩溪,于是被迫代替她去往敵國(guó)和親浅役。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,037評(píng)論 2 355

推薦閱讀更多精彩內(nèi)容