3. 無重復(fù)字符的最長子串

難度中等4774

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

示例 1:

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

示例 2:

輸入: s = "bbbbb"
輸出: 1
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "b"，所以其長度為 1。

示例 3:

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

示例 4:

輸入: s = ""
輸出: 0

提示：

• 0 <= s.length <= 5 * 10<sup>4</sup>
• s 由英文字母、數(shù)字、符號(hào)和空格組成

My solution

import java.util.Arrays;
public class Solution {
    public int lengthOfLargestSubstring(String s){
        if(s.length()==0)
            return 0;
        int[] count=new int[s.length()];
        String tmp = null;
        for(int i=0;i<s.length();i++){
            tmp="";
            for(int j=i;j<s.length();j++){
                if (tmp.contains(String.valueOf(s.charAt(j))))
                    break;
                else
                {
                    tmp+=s.charAt(j);
                    count[i]++;
                }
            }
        }
        Arrays.sort(count);
        return count[s.length()-1];
    }
}

執(zhí)行用時(shí)：360 ms, 在所有 Java 提交中擊敗了5.20%的用戶
內(nèi)存消耗：39.3 MB, 在所有 Java 提交中擊敗了9.11%的用戶
時(shí)間復(fù)雜度O(n^2)
空間復(fù)雜度O(n)

滑動(dòng)窗口法

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 哈希集合，記錄每個(gè)字符是否出現(xiàn)過
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指針，初始值為 -1，相當(dāng)于我們?cè)谧址淖筮吔绲淖髠?cè)，還沒有開始移動(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è)極長的無重復(fù)字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }
}

i是窗口的左指針，rk是窗口的右指針，其中i是所指元素的序號(hào)，從0開始，而rk是所指元素序號(hào)-1.從-1開始；
剛開始i=0，不用從窗口去掉最左側(cè)元素，而之后就需要移動(dòng)左指針了；
當(dāng)rk<s.length()-1并且哈希集合中不包含序號(hào)為rk+1的元素時(shí)，將這個(gè)元素添加進(jìn)哈希集合，并且移動(dòng)右指針；
在一次移動(dòng)左指針的過程中，最后要給ans重新賦值，保證ans最后為滑動(dòng)窗口的最大距離；
滑動(dòng)窗口法的關(guān)鍵在于當(dāng)?shù)趇個(gè)元素到第rk+1個(gè)元素，第rk+1的元素為最先出現(xiàn)的相同元素時(shí)，只需要將i向右移動(dòng)一個(gè)位置，而不需要移動(dòng)rk，因?yàn)榇藭r(shí)i+1到rk之間肯定是沒有重復(fù)字符的

作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2/