|
一.算法題 題目 Given a string, find the length of the longest substring without repeating characters. Example 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 Note that the answer must be a substring, 'pwke' is a subsequence and not a substring.
二.算法題解讀 題目大意:給定一個(gè)字符串,找出不含有重復(fù)字符的最長(zhǎng)子串的長(zhǎng)度 解讀Example 給定'abcabcbb',沒(méi)有重復(fù)字符的最長(zhǎng)子串是'abc',那么長(zhǎng)度就是3 給定'bbbbb',最長(zhǎng)子串就是'b',長(zhǎng)度就是1 給定pwwkew,最長(zhǎng)子串就是'wke',長(zhǎng)度為3, 注意,必須是一個(gè)子串.'pwke',是子序列,而不是子串
三.'滑動(dòng)窗口'優(yōu)化解決 使用暴力法解決是非常簡(jiǎn)單,但是在暴力法中我們會(huì)反復(fù)檢查一個(gè)子字符串是否含有重復(fù)的字符.但其實(shí)沒(méi)有這個(gè)必要.
四.前導(dǎo)關(guān)鍵詞介紹 HashSet是Java中實(shí)現(xiàn)Set接口.由哈希表支持.它不保證Set的迭代順序,但是它利用Hash的原理來(lái)確保元素的唯一性.在HashSet中,元素都存到HashMap鍵值對(duì)的key上面.而Value時(shí)有一個(gè)統(tǒng)一的Hash值.
當(dāng)有新的值加入時(shí),底層的HashMap會(huì)判斷Key值是否存在,如果不存在則插入新值.同時(shí)這個(gè)插入的細(xì)節(jié)會(huì)按照HashMap插入細(xì)節(jié).如果存在則不插入.
滑動(dòng)窗口:是指的是數(shù)組/字符串問(wèn)題的常用抽象概念.窗口通常在數(shù)組/字符串中由開(kāi)始和結(jié)束的索引定義的一系列元素的集合.即可[i,j)(左閉,右開(kāi)).而滑動(dòng)窗口是可以將2個(gè)邊界向某一個(gè)方向'滑動(dòng)'的窗口.例如,我們將[i,j)向右滑動(dòng)1個(gè)元素,則它將變成[i+1,j+1)(左閉,右開(kāi));
四.思路 如果從索引i到j(luò)-1之間的子字符串S[ij]已經(jīng)被檢查為沒(méi)有重復(fù)字符.那則只需要檢查s[j]對(duì)應(yīng)的字符是否存在于子字符串s[ij]; 由于在C語(yǔ)言中是沒(méi)有集合這一個(gè)概念的.所以我們使用java來(lái)實(shí)現(xiàn).我們可以通過(guò)HashSet作為活動(dòng)窗口.那我們只需要用O(1)的時(shí)間來(lái)完成對(duì)字符是否在當(dāng)前子字符串的檢查. 我們使用HashSet將字符存儲(chǔ)在當(dāng)前窗口[i,j),最初i=j .然后我們向右側(cè)滑動(dòng)索引j,如果它不在HashSet中,則我們會(huì)繼續(xù)滑動(dòng)j.直到s[j]已經(jīng)存在于HashSet中,此時(shí),我們就已經(jīng)找到的沒(méi)有重復(fù)字符的最長(zhǎng)子串將會(huì)以索引i開(kāi)頭.如果我們將所有的i,都做如此操作即可得到結(jié)果. 五.實(shí)現(xiàn) Java Code 
六.復(fù)雜度分析 時(shí)間復(fù)雜度:o(2n) = o(n);在最糟糕的情況下,每個(gè)字符頂多被i,j訪問(wèn)2次. 空間復(fù)雜度:o(min(m,n)).窗口滑動(dòng)法需要O(K)的空間,K指的是集合大小.而集合的大小取決于字符串n的大小以及字符串集的大小.
小編OS:如有疑問(wèn),留言即可.胖C會(huì)利用空余時(shí)間給大家做一個(gè)簡(jiǎn)單解答的.
持續(xù)更新關(guān)注公眾號(hào)!
|
