3.?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?subsequenceand not a substring.

問題描述，返回一個(gè)字符串中，不包含重復(fù)字符，最長的子字符串的長度。

例如，"pwwkew"，最長的不重復(fù)的字符串就是wke，所以返回3.

解法1：

這個(gè)方法可能是大部分第一時(shí)間想到的，定義一個(gè)空數(shù)組，然后定義????i=0,????j=i+1，兩個(gè)循環(huán)嵌套，然后判斷數(shù)組是否包含，如果不包含，加入數(shù)組，包含，就退出第二層循環(huán)，比較上一次的長度。這個(gè)方法的時(shí)間復(fù)雜度要有n的3次方，所以不推介。

解法2：

其實(shí)這是一個(gè)數(shù)學(xué)問題。相應(yīng)最簡單的解法，就是定義i=0，j=0然后定義一個(gè)HashSet，然后從j=0開始遍歷數(shù)組，當(dāng)這個(gè)值不在Set里面，那么就加入，然后j++。如果已經(jīng)包含了這個(gè)值，那么不加入，并且，把Set刪除 i 所在位置的值，然后i++。

其實(shí)就是要如果這個(gè)值不存在于Set中就加入，已經(jīng)存在，那么我們叫減少Set的值。具體可以自己寫一個(gè)字符串，然后一步步操作，就能明白了。