📢前言

• 🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻
• 🌲 每天打卡一道算法題，既是一個學(xué)習(xí)過程，又是一個分享的過程😜
• 🌲 提示：本專欄解題 編程語言一律使用 C# 和 Java 兩種進行解題
• 🌲 要保持一個每天都在學(xué)習(xí)的狀態(tài)，讓我們一起努力成為算法大神吧🧐！
• 🌲 今天是力扣算法題持續(xù)打卡第3天🎈！
• 🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻

🌲原題樣例

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

示例 1:

• 輸入: s = “abcabcbb”
• 輸出: 3
• 解釋: 因為無重復(fù)字符的最長子串是 “abc”，所以其長度為 3,。

示例 2:

• 輸入: s = “bbbbb”
• 輸出: 1
• 解釋: 因為無重復(fù)字符的最長子串是 “b”，所以其長度為 1。

示例 3:

• 輸入: s = “pwwkew”
• 輸出: 3
• 解釋: 因為無重復(fù)字符的最長子串是 “wke”，所以其長度為 3,。
  請注意，你的答案必須是 子串 的長度，“pwke” 是一個子序列，不是子串,。

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母,、數(shù)字、符號和空格組成

🌻C#方法一：索引尋找

首先直接遍歷所有字符，然后當(dāng)碰到重復(fù)字符時存儲值，同時處理List，進行下一隊的查找,。

public class Solution {
public int LengthOfLongestSubstring(string s) {

        List<char> ls = new List<char>();
        int n = s.Length;
        int intMaxLength = 0;

        for (int i = 0; i < n; i++)
        {
            if (ls.Contains(s[i]))
            {
                ls.RemoveRange(0, ls.IndexOf(s[i]) + 1);
            }
            ls.Add(s[i]);
            intMaxLength = ls.Count > intMaxLength ? ls.Count : intMaxLength;
        }

        return intMaxLength;
    }
    }

執(zhí)行結(jié)果

執(zhí)行通過，執(zhí)行用時76ms，內(nèi)存消耗25MB.

🌻C#方法二：滑動窗口

滑動窗口算法（Sliding Window）可以用來解決字符串（數(shù)組）的子元素問題，，查找滿足一定條件的連續(xù)子區(qū)間，可以將嵌套的循環(huán)問題，轉(zhuǎn)化為單循環(huán)問題，降低時間復(fù)雜度,。

滑動窗口算法需要用到雙指針，遍歷字符串（數(shù)組）時，兩個指針都起始于原點，并一前一后地向終點移動，兩個指針一前一后夾著的子串（子數(shù)組）就像一個窗口，窗口的大小和覆蓋范圍會隨著前后指針的移動而發(fā)生變化。

窗口該如何移動需要根據(jù)求解的問題來決定，通過左右指針的移動遍歷字符串（數(shù)組），尋找滿足特定條件的連續(xù)子區(qū)間,。

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        HashSet<char> letter = new HashSet<char>();// 哈希集合，記錄每個字符是否出現(xiàn)過
        int left = 0,right = 0;//初始化左右指針，指向字符串首位字符
        int length = s.Length;
        int count = 0,max = 0;//count記錄每次指針移動后的子串長度
        while(right < length)
        {
            if(!letter.Contains(s[right]))//右指針字符未重復(fù)
            {
                letter.Add(s[right]);//將該字符添加進集合
                right++;//右指針繼續(xù)右移
                count++;
            }
            else//右指針字符重復(fù)，左指針開始右移，直到不含重復(fù)字符（即左指針移動到重復(fù)字符(左)的右邊一位）
            { 
                letter.Remove(s[left]);//去除集合中當(dāng)前左指針字符
                left++;//左指針右移
                count--;
            }
            max = Math.Max(max,count);
        }
        return max;
    }
}

執(zhí)行結(jié)果

執(zhí)行通過，執(zhí)行用時68ms，內(nèi)存消耗25.6MB.

🌻Java方法一：滑動窗口

思路和算法
這是力扣官方解法中的，直接Copy過來看一下！
我們先用一個例子考慮如何在較優(yōu)的時間復(fù)雜度內(nèi)通過本題,。

我們不妨以示例一中的字符串 \texttt{abcabcbb}abcabcbb 為例，找出從每一個字符開始的，不包含重復(fù)字符的最長子串，那么其中最長的那個字符串即為答案。對于示例一中的字符串，我們列舉出這些結(jié)果，其中括號中表示選中的字符以及最長的字符串：

• 以 \texttt{(a)bcabcbb}(a)bcabcbb 開始的最長字符串為 \texttt{(abc)abcbb}(abc)abcbb；
• 以 \texttt{a(b)cabcbb}a(b)cabcbb 開始的最長字符串為 \texttt{a(bca)bcbb}a(bca)bcbb；
• 以 \texttt{ab?abcbb}ab?abcbb 開始的最長字符串為 \texttt{ab(cab)cbb}ab(cab)cbb；
• 以 \texttt{abc(a)bcbb}abc(a)bcbb 開始的最長字符串為 \texttt{abc(abc)bb}abc(abc)bb；
• 以 \texttt{abca(b)cbb}abca(b)cbb 開始的最長字符串為 \texttt{abca(bc)bb}abca(bc)bb；
• 以 \texttt{abcab?bb}abcab?bb 開始的最長字符串為 \texttt{abcab(cb)b}abcab(cb)b；
• 以 \texttt{abcabc(b)b}abcabc(b)b 開始的最長字符串為 \texttt{abcabc(b)b}abcabc(b)b；
• 以 \texttt{abcabcb(b)}abcabcb(b) 開始的最長字符串為 \texttt{abcabcb(b)}abcabcb(b),。

這樣一來，我們就可以使用「滑動窗口」來解決這個問題了：

• 我們使用兩個指針表示字符串中的某個子串（或窗口）的左右邊界，其中左指針代表著上文中「枚舉子串的起始位置」，而右指針即為上文中的 r_kr k ；

• 在每一步的操作中，我們會將左指針向右移動一格，表示 我們開始枚舉下一個字符作為起始位置，然后我們可以不斷地向右移動右指針，但需要保證這兩個指針對應(yīng)的子串中沒有重復(fù)的字符,。在移動結(jié)束后，這個子串就對應(yīng)著 以左指針開始的，不包含重復(fù)字符的最長子串。我們記錄下這個子串的長度；

• 在枚舉結(jié)束后，我們找到的最長的子串的長度即為答案,。

判斷重復(fù)字符

在上面的流程中，我們還需要使用一種數(shù)據(jù)結(jié)構(gòu)來判斷 是否有重復(fù)的字符，常用的數(shù)據(jù)結(jié)構(gòu)為哈希集合（即 C++ 中的 std::unordered_set，Java 中的 HashSet，Python 中的 set, JavaScript 中的 Set）,。在左指針向右移動的時候，我們從哈希集合中移除一個字符，在右指針向右移動的時候，我們往哈希集合中添加一個字符。

至此，我們就完美解決了本題

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

執(zhí)行結(jié)果

執(zhí)行通過，執(zhí)行用時6ms，內(nèi)存消耗38.3 MB.

🌻Java方法二：遍歷

總體思路
遍歷字符串，每次以 i 值記錄，不回溯 i 值，用flag記錄遍歷過程找到的重復(fù)的字符的位置,。如果遇到重復(fù)字符，i-flag 即為子串長度，此時flag重新定位到子串中重復(fù)字符的位置，i 繼續(xù)往后遍歷,。這里length跟result記錄長度。我感覺代碼可以更簡潔一點的，但是好像寫懵了？

圖解

class Solution {
  public int lengthOfLongestSubstring(String s) {
        //a b c a b c d a d e
        //0 1 2 3 4 5 6 7 8 9
        int maxSize = 0;
        //記錄ASCII 碼字符出現(xiàn)的位置，以字符作為下標
        int[] dict = new int[128];
        //為了方便理解，這里把數(shù)組內(nèi)容全部設(shè)為 -1，之后在記錄的時候就可以從 0 開始，方便理解
        Arrays.fill(dict, -1);
        //用于記錄重復(fù) ASCII 碼字符出現(xiàn)的位置的值
        int repeatValue = -1;
        // 當(dāng)前下標
        int i = 0;
        int ASCII;
        while (i < s.length()) {
            ASCII = s.charAt(i);
            //如果當(dāng)前位置的值 > repeatValue，證明當(dāng)前位置已經(jīng)賦過一次值了，證明字符重復(fù)
            if (dict[ASCII] > repeatValue)
                //更新 repeatValue 為之前賦值的下標
                repeatValue = dict[ASCII];
            //將當(dāng)前下標賦值到數(shù)組相應(yīng)位置
            dict[ASCII] = i;
            //i - repeatValue(去除重復(fù)部分)
            // 比如 abcabcdade 中的三個 a 的計算  abca - a(3 - 0)=bca   abcabcda - abca(7 - 3)=bcda
            maxSize = Math.max(maxSize, i - repeatValue);
            //s.length() - repeatValue - 1 判斷剩下的數(shù)有沒有必要繼續(xù)循環(huán)
            //比如 abcabcdade 最后的 a(當(dāng) i = 7 repeatValue = 3) ，abcabcdade - abca(10-3-1) = bcdade  剩下最多有六位
            //比如 abcabcdade 最后的 d(當(dāng) i = 8 repeatValue = 6) ，abcabcdade - abcabcd(10-6-1) = ade  剩下最多也是三位
            if (maxSize >= s.length() - repeatValue - 1) {
                return maxSize;
            }
            i++;
        }
        return maxSize;
    }
}

執(zhí)行結(jié)果

執(zhí)行通過，執(zhí)行用時2ms，內(nèi)存消耗42.68 MB.

💬總結(jié)

• 今天是力扣算法題打卡的第三天！
• 文章采用 C# 和 Java 兩種編程語言進行解題
• 一些方法也是參考力扣大神寫的，也是邊學(xué)習(xí)邊分享，再次感謝算法大佬們
• 那今天的算法題分享到此結(jié)束啦，明天再見！