方法一：暴力 + 切片

枚舉滑動窗口的做端點(diǎn)，采用基地址 + 偏移量【滑動數(shù)組長度】的方式，對原字符串切片，利用哈希表計數(shù)，只要出現(xiàn)次數(shù)等于2則將其加入返回值中。

Python版本

C++版本

復(fù)雜度分析

• 時間復(fù)雜度：O(N)。此處 n 指的是字符串 s 的最大長度，加之每次取得長度為 10 的子字符串，實際復(fù)雜度應(yīng)為 10N。

• 空間復(fù)雜度：O(N)?；瑒哟翱跒?0，每一個位序可能有四種填充字符，可能的組合共有 4 ^ 10，1048576，約等于10N.

方法二：哈希映射 + 位運(yùn)算 + 滑動窗口

四種字符，若使用二進(jìn)制表達(dá)，需要 \log_{2}{x}位，即四位。分別將其映射為二進(jìn)制數(shù)0, 1, 10, 11， 顯然需要 k * 2 = 20二進(jìn)制位表達(dá)一個滑動窗口；

設(shè)若存在十進(jìn)制表達(dá)的二進(jìn)制數(shù)：x。首先計算前 9 個字符的二進(jìn)制值，每一次先將 x 的二進(jìn)制數(shù)向左移動兩位，將從字符串 s 中取得的字符，經(jīng)過哈希映射后，使用按位或運(yùn)算改寫到 x 的二進(jìn)制數(shù)的最低兩位中，循環(huán)往復(fù)，直到 9 個字符全部加入到 x 的二進(jìn)制表達(dá)中。

在使用滑動窗口時，總的原則是套用隊列入隊的概念，入隊，出隊方向分別對應(yīng)二進(jìn)制的最低兩位和最高兩位，以下操作將以隊列術(shù)語代替。當(dāng)滑動窗口向右滑動時，將當(dāng)前遍歷到的字符，經(jīng)過哈希映射后轉(zhuǎn)義，將其通過按位或運(yùn)算入隊，同時制造一個容器 Y：二進(jìn)制位等于20，全為1的二進(jìn)制數(shù)。

出隊將用位運(yùn)算中的按位與運(yùn)算實現(xiàn)。

我們知道，在與運(yùn)算中，若二進(jìn)制位長度不一，存在著高位補(bǔ)零和高位截斷的兩種操作，前者適用于滑動礦口長度小于等于9的情況，后者適用于滑動窗口長度大于等于10的情況。

構(gòu)造容器Y時，首先將 1 向左位移 k * 2 的位，即20位。此時二進(jìn)制位長度為21位，將其減一，得到20位，每一個位均為1的容器。

Python版本

C++版本

復(fù)雜度分析

• 時間復(fù)雜度：O(N)。此處 n 指的是字符串 s 的最大長度，加之每次取得長度為 10 的子字符串，實際復(fù)雜度應(yīng)為 10N。

• 空間復(fù)雜度：O(N)?；瑒哟翱跒?0，每一個位序可能有四種填充字符，可能的組合共有 4 ^ 10，1048576，約等于10N.

圖示