Pythonで一意な要素がちょうどk個のサブリストの数を数える方法【スライディングウィンドウ】

数値リスト nums と整数 k が与えられたとき、連続する部分リスト(サブリスト)に含まれる一意な要素がちょうど k 個であるものの総数を求める問題です。

たとえば、入力が nums = [2, 2, 3, 4]、k = 2 の場合、条件を満たすサブリストは [2, 2, 3]、[2, 3]、[3, 4] の3つなので、出力は 3 になります。

解法のアプローチ:スライディングウィンドウ

この問題は「スライディングウィンドウ(尺取り法)」を使うと O(n) で効率的に解けます。ポイントは、「ちょうど k 個」のサブリストを直接数えるのではなく、「一意な要素が最大 k 個以下のサブリストの数」から「最大 k−1 個以下のサブリストの数」を差し引くことで求める点です。

アルゴリズムの手順

1. 関数 count(K) を定義する。これは「一意な要素が最大 K 個以下であるサブリストの数」を返します。
2. slot:各要素の出現回数を記録するマップ(Counter)を用意する(デフォルト値は 0)。
3. 左端ポインタ i と結果 res を 0 で初期化する。
4. 右端 j を動かしながら、各要素 x に対して次を繰り返す。
   • slot[x] を 1 増やす。
   • ウィンドウ内の一意な要素数が K を超えている間、左端 nums[i] の出現回数を 1 減らし、0 になったらマップから削除して i を進める。
   • res += j - i + 1(右端 j を含む有効なサブリストの数を加算)。
5. res を返す。
6. メイン処理では count(k) - count(k - 1) を返す。

Pythonでの実装例

以下のコードで実際の動作を確認できます。

from collections import Counter
class Solution:
   def solve(self, nums, k):
      def count(K):
         slot = Counter()
         i = res = 0
         for j, x in enumerate(nums):
            slot[x] += 1
            while len(slot) > K:
               slot[nums[i]] -= 1
               if slot[nums[i]] == 0:
                  del slot[nums[i]]
               i += 1
            res += j - i + 1
         return res
      return count(k) - count(k - 1)
ob = Solution()
nums = [2, 2, 3, 4]
k = 2
print(ob.solve(nums, k))

入力

[2, 2, 3, 4], 2

出力

3

計算量について

左右のポインタ i と j はそれぞれ最大でも配列の長さ分しか移動しないため、全体の計算量は O(n)、要素カウント用のマップが必要とする追加メモリは O(n) です。全サブリストを総当たりする O(n²) 以上の素朴な手法と比べ、大きな入力でも高速に動作します。