如何使用 C# 從給定的字串中查詢不重複字元的最長子串的長度?


透過使用滑動視窗技術,讓 2 個指標 i 和 j 從給定的字串輸入中查詢不重複字元的最長子串。i 和 j 都指向字串中的相同字元。遍歷字串並將它新增到列表中。如果找到重複的字元,則從列表中將它刪除,否則附加到列表中。

示例 1

輸入 − s = "abcabcbb"

輸出 − 3

說明 − 答案是 "abc",長度為 3。

示例 2

輸入 − s = "bbbbb"

輸出 − 1

說明 − 答案是 "b",長度為 1。

時間複雜度 − O(N)

空間複雜度 − O(N)

示例

public class Arrays{
   public int LongestSubstringWithNoRepeatingCharacters(string s){
      List<char> c = new List<char>();
      int iPointer = 0;
      int jpointer = 0;
      int max = 0;
      while (jpointer < s.Length){
         if (c.Contains(s[jpointer])){
            c.Remove(s[iPointer]);
            iPointer++;
         }
         else{
            max = Math.Max(c.Count(), max);
            c.Add(s[jpointer]);
            jpointer++;
         }
      }
      return max;
   }
}

static void Main(string[] args){
   int res = s.LongestSubstringWithNoRepeatingCharacters("abcabcbb");
   Console.WriteLine(res);
}

輸出

2

更新於:2021 年 8 月 17 日

1000 多次瀏覽

開啟你的 職業生涯

完成課程獲得認證

開始學習
廣告