一、問(wèn)題

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

1??示例 1：輸入：s = "abcabcbb"，輸出：3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "abc"，所以其長(zhǎng)度為 3。

2??示例 2：輸入：s = "aaaaaa"，輸出：1
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "b"，所以其長(zhǎng)度為 1。

3??示例 3：輸入：s = "pwwkew"，輸出：3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "wke"，所以其長(zhǎng)度為 3。
請(qǐng)注意，你的答案必須是 子串 的長(zhǎng)度，"pwke" 是一個(gè)子序列，不是子串。

4??示例 4：輸入：s = ""，輸出：0

二、解答

測(cè)試主類(lèi)：

public static void main(String args[]) {
    String str = "abcabcbb";
    System.out.println(lengthOfLongestSubstring(str));
    String str1 = "aaaaaa";
    System.out.println(lengthOfLongestSubstring(str1));
    String str2 = "pwwkew";
    System.out.println(lengthOfLongestSubstring(str2));
}

1??滑動(dòng)窗口

對(duì)于示例一中的字符串，列舉出結(jié)果，其中括號(hào)中表示選中的字符以及最長(zhǎng)的字符串：

以 (a)bcabcbb 開(kāi)始的最長(zhǎng)字符串為 (abc)abcbb；
以 a(b)cabcbb 開(kāi)始的最長(zhǎng)字符串為 a(bca)bcbb；
以 ab(c)abcbb 開(kāi)始的最長(zhǎng)字符串為 ab(cab)cbb；
以 abc(a)bcbb 開(kāi)始的最長(zhǎng)字符串為 abc(abc)bb；
以 abca(b)cbb 開(kāi)始的最長(zhǎng)字符串為 abca(bc)bb；
以 abcab(c)bb 開(kāi)始的最長(zhǎng)字符串為 abcab(cb)b；
以 abcabc(b)b 開(kāi)始的最長(zhǎng)字符串為 abcabc(b)b；
以 abcabcb(b) 開(kāi)始的最長(zhǎng)字符串為 abcabcb(b)。

如果依次遞增枚舉子串的起始位置，那么子串的結(jié)束位置也是遞增的！原因在于，假設(shè)選擇字符串中的第 k 個(gè)字符作為起始位置，并且得到了不包含重復(fù)字符的最長(zhǎng)子串的結(jié)束位置為 rk。那么當(dāng)選擇第 k+1 個(gè)字符作為起始位置時(shí)，首先從 k+1 到 rk 的字符顯然是不重復(fù)的，并且由于少了原本的第 k 個(gè)字符，可以嘗試?yán)^續(xù)增大 rk?，直到右側(cè)出現(xiàn)了重復(fù)字符為止。如此，就可以使用「滑動(dòng)窗口」來(lái)解決這個(gè)問(wèn)題了：

1. 使用兩個(gè)指針表示字符串中的某個(gè)子串的左右邊界。其中左指針代表「枚舉子串的起始位置」，而右指針即為上文中的 rk。
2. 在每一步的操作中，將左指針向右移動(dòng)一格，表示開(kāi)始枚舉下一個(gè)字符作為起始位置，然后不斷地向右移動(dòng)右指針，但需要保證這兩個(gè)指針對(duì)應(yīng)的子串中沒(méi)有重復(fù)的字符。在移動(dòng)結(jié)束后，這個(gè)子串就對(duì)應(yīng)著以左指針開(kāi)始的，不包含重復(fù)字符的最長(zhǎng)子串。記錄下這個(gè)子串的長(zhǎng)度。
3. 在枚舉結(jié)束后，找到的最長(zhǎng)的子串的長(zhǎng)度即為答案。

注意：判斷重復(fù)字符需要使用一種數(shù)據(jù)結(jié)構(gòu)來(lái)判斷是否有重復(fù)的字符，常用的數(shù)據(jù)結(jié)構(gòu)為哈希集合如 Java 中的 HashSet。在左指針向右移動(dòng)的時(shí)候，從哈希集合中移除一個(gè)字符，在右指針向右移動(dòng)的時(shí)候，往哈希集合中添加一個(gè)字符。

public static int lengthOfLongestSubstring(String s) {
    // 哈希集合，記錄每個(gè)字符是否出現(xiàn)過(guò)
    Set<Character> occ = new HashSet<>();
    int n = s.length();
    // 右指針，初始值為 -1，相當(dāng)于在字符串的左邊界的左側(cè)，還沒(méi)有開(kāi)始移動(dòng)
    int rk = -1, ans = 0;
    for (int i = 0; i < n; ++i) {
        if (i != 0) {
            // 左指針向右移動(dòng)一格，移除一個(gè)字符
            occ.remove(s.charAt(i - 1));
        }
        while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
            // 不斷地移動(dòng)右指針
            occ.add(s.charAt(rk + 1));
            ++rk;
        }
        // 第 i 到 rk 個(gè)字符是一個(gè)極長(zhǎng)的無(wú)重復(fù)字符子串
        ans = Math.max(ans, rk - i + 1);
    }
    return ans;
}

①時(shí)間復(fù)雜度：O(N)，其中 N 是字符串的長(zhǎng)度。左指針和右指針?lè)謩e會(huì)遍歷整個(gè)字符串一次。
②空間復(fù)雜度：O(∣Σ∣)，其中 ∣Σ∣表示字符集(即字符串中可以出現(xiàn)的字符)，∣Σ∣表示字符集的大小。在本題中沒(méi)有明確說(shuō)明字符集，因此可以默認(rèn)為所有 ASCII 碼在 [0, 128) 內(nèi)的字符，即∣Σ∣=128。需要用到哈希集合來(lái)存儲(chǔ)出現(xiàn)過(guò)的字符，而字符最多有∣Σ∣ 個(gè)，因此空間復(fù)雜度為 O(∣Σ∣)。

2??滑動(dòng)窗口

1. 首先，判斷當(dāng)前字符是否包含在map中，如果不包含，將該字符添加到map(字符，字符在數(shù)組下標(biāo))，此時(shí)沒(méi)有出現(xiàn)重復(fù)的字符，左指針不需要變化。此時(shí)不重復(fù)子串的長(zhǎng)度為：i-left+1，與原來(lái)的 maxLen 比較，取最大值。

2. 如果當(dāng)前字符 ch 包含在 map 中，此時(shí)有兩種情況：
   1）當(dāng)前字符包含在當(dāng)前有效的子段中，如：abca，當(dāng)遍歷到第二個(gè)a，當(dāng)前有效最長(zhǎng)子段是 abc，又遍歷到a，那么此時(shí)更新 left 為 map.get(a)+1=1，當(dāng)前有效子段更新為 bca；
   2）當(dāng)前字符不包含在當(dāng)前最長(zhǎng)有效子段中，如：abba，先添加 a、b 進(jìn) map，此時(shí) left=0，再添加 b，發(fā)現(xiàn) map 中包含b，而且 b 包含在最長(zhǎng)有效子段中，就是1）的情況，更新 left=map.get(b)+1=2，此時(shí)子段更新為 b，而且map 中仍然包含 a，map.get(a)=0。隨后，遍歷到 a，發(fā)現(xiàn) a 包含在 map 中，且 map.get(a)=0，如果像1）一樣處理，就會(huì)發(fā)現(xiàn) left=map.get(a)+1=1，實(shí)際上，left 此時(shí)應(yīng)該不變，left 始終為2，子段變成 ba 才對(duì)。

為了處理以上兩類(lèi)情況，每次更新 left，left=Math.max(left , map.get(ch)+1)。另外，更新 left 后，不管原來(lái)的 s.charAt(i) 是否在最長(zhǎng)子段中，都要將 s.charAt(i) 的位置更新為當(dāng)前的 i，因此此時(shí)新的 s.charAt(i) 已經(jīng)進(jìn)入到當(dāng)前最長(zhǎng)的子段中！

public static int lengthOfLongestSubstring(String s) {
    if (s.length() == 0) return 0;
    HashMap<Character, Integer> map = new HashMap<>();
    int max = 0;
    int left = 0;//滑動(dòng)窗口左下標(biāo)，i相當(dāng)于滑動(dòng)窗口右下標(biāo)
    for (int i = 0; i < s.length(); i++) {
        //charAt()用于返回指定索引處的字符。索引范圍為從 0 到 length() - 1。
        if (map.containsKey(s.charAt(i))) {
            //map.get()返回字符所對(duì)應(yīng)的索引，當(dāng)發(fā)現(xiàn)重復(fù)元素時(shí)，窗口左指針右移
            left = Math.max(left, map.get(s.charAt(i)) + 1);
        }
        //再更新map中a映射的下標(biāo)
        map.put(s.charAt(i), i);
        //比較兩個(gè)參數(shù)的大小
        max = Math.max(max, i - left + 1);
    }
    return max;
}