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