1876. 長度為三且各字符不同的子字符串

對讀者的要求

• 了解for, while兩種循環(huán)結構；

• 或許在游戲中拿過三殺；

• 能夠計算簡單組合數(shù)；

題意簡述

找出長度為3的連續(xù)字符串的個數(shù)；

字符串長度的值域 [1, 100]。

方法一：雙指針

從頭開始遍歷，取連續(xù)的三個字符，統(tǒng)計個數(shù)；

Python版本

C++版本

復雜度分析

• 時間復雜度：O(N)。此處的 n 指的是字符串 s 的長度，實際上只會運行 n - 3 次。

• 空間復雜度：O(1)。使用一個長度為3的哈希表，作為一個滑動數(shù)組空間，將會使用 n - 3次。

備注

• 兩次debug： 沒有閱讀題目下面的限制條件，s 的長度可以為1，而支撐判斷需要至少三個字符，因此需要特判；

• 主串無需遍歷全串，連續(xù)串從0位序開始，最多遍歷到 n - 3；

方法二：遍歷 + 判斷

遍歷連續(xù)字符串，判斷他們三個數(shù)組成的長度為2，數(shù)量為3的數(shù)對，是否每個數(shù)對都不相等；

Python版本

C++版本

復雜度分析

• 時間復雜度： O(n)。此處的長度n 指的是 字符串s長度為n。 但僅需要遍歷到 n - 2的位置

• 空間復雜度： O(1)。

備注

• 對于 C++ 而言，如果在for循環(huán)中將s.length()的值作為上限，可能導致堆棧溢出；

• 導致堆棧溢出的原因是 unsigned int可能由負數(shù)直接轉換為較大正數(shù)，從而導致程序出錯，測試代碼如下：

• 因此先使用一個變量【確定的數(shù)據類型】，保存s.length()的值，然后再放入循環(huán)中進行遍歷,雖未找到原因，但官解中經常遇到這樣的寫法；