來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

題目描述

給定一個字符串 s ，請你找出其中不含有重復(fù)字符的 最長子串 的長度艘狭。

題目分析

滑動窗口

思路：兩個指針表示字符串中的某個子串（或窗口）的左右邊界。左指針向右移動一格，移除一個字符；不斷向右移動 右指針杈帐。哈希集合燃乍，記錄每個字符是否出現(xiàn)過，

代碼實(shí)現(xiàn)

public class LengthOfLongestSubstring_3 {

    public static void main(String[] args) {
        LengthOfLongestSubstring_3 main = new LengthOfLongestSubstring_3();
        int result = main.lengthOfLongestSubstring("abcdee");
        System.out.println("result:" + result);
    }


    public int lengthOfLongestSubstring(String s) {
        int result = 0;
        int end = 0;
        // 哈希集合港华，記錄每個字符是否出現(xiàn)過
        Set<Character> occ = new HashSet<Character>();
        for (int i = 0; i < s.length(); i++) {
            if (i > 0) {
                // 左指針向右移動一格，移除一個字符
                occ.remove(s.charAt(i - 1));
            }
            // 不斷向右移動 右指針
            while (end < s.length() && !occ.contains(s.charAt(end))){
                occ.add(s.charAt(end));
                end++;
            }
            int length = end - I;
            if (result < length) {
                result = length;
            }

        }
        return result;
    }

    /**
     * 效率太低
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring1(String s) {
        int result = 0;
        int length = 0;
        int nextEndStart = 0;

        // 哈希集合午衰，記錄每個字符是否出現(xiàn)過
        Set<Character> occ = new HashSet<Character>();
        for (int i = 0; i < s.length(); i++) {
            if (i > 0) {
                // 左指針向右移動一格立宜，移除一個字符
                occ.remove(s.charAt(i - 1));
            }

            // 不斷向右移動 右指針
            for (int end = nextEndStart; end < s.length(); end++) {
                if (occ.contains(s.charAt(end))) {
                    length = end - I;
                    nextEndStart = end;
                    break;
                }
                occ.add(s.charAt(end));
                if(end == s.length() - 1){
                    length =  end - i + 1;
                }
            }
            if (result < length) {
                result = length;
            }
        }

        System.out.println("result:" + result);
        return result;
    }

}

運(yùn)行結(jié)果：

復(fù)雜度

• 時間復(fù)雜度：O(n)冒萄，其中 n 是字符串長度。
• 空間復(fù)雜度：O(∣Σ∣)橙数，其中 Σ 表示字符集（即字符串中可以出現(xiàn)的字符）尊流，
  ∣Σ∣ 表示字符集的大小。在本題中沒有明確說明字符集灯帮，因此可以默認(rèn)為所有 ASCII 碼在 [0,128) 內(nèi)的字符奠旺，即 ∣Σ∣=128。我們需要用到哈希集合來存儲出現(xiàn)過的字符施流，而字符最多有 ∣Σ∣ 個响疚，因此空間復(fù)雜度為 O(∣Σ∣)。

好了瞪醋，今天就到這里忿晕，感謝各位看官到這里，不如點(diǎn)個關(guān)注吧银受！
?