Pythonでサイズkの各ウィンドウに含まれる一意な要素の数を求めるプログラム

数値のリスト nums と整数 k が与えられたとき、サイズ k の各ウィンドウ（連続する k 個の要素）に含まれる異なる数値（ユニークな要素）の個数を順番に求める問題です。

問題の例

たとえば、入力が nums = [2, 2, 3, 3, 4]、k = 2 の場合を考えてみましょう。このとき、各ウィンドウは次のようになります。

• [2, 2] → 一意な要素数は 1（2のみ）
• [2, 3] → 一意な要素数は 2（2と3）
• [3, 3] → 一意な要素数は 1（3のみ）
• [3, 4] → 一意な要素数は 2（3と4）

したがって、出力は [1, 2, 1, 2] となります。

解き方のアプローチ

この問題は「スライディングウィンドウ」という手法を使うことで効率的に解けます。ウィンドウが1つずれるたびに、全体を再カウントするのではなく、入ってくる要素を1つ追加し、出ていく要素を1つ削除するだけです。手順は以下の通りです。

• まず、最初の k 個の要素について、各要素の出現回数を記録した辞書（Counter）を作成します。
• 結果を格納する空のリスト ans を用意します。
• i を k から nums の末尾まで繰り返します。
  • 現在の辞書のサイズ（＝一意な要素数）を ans の末尾に追加します。
  • 新しい要素 nums[i] のカウントを +1 します。
  • ウィンドウから外れる要素 nums[i - k] のカウントを -1 します。
  • そのカウントが 0 になった場合は、辞書から該当キーを削除します（これにより、辞書のサイズが常に「一意な要素数」を正確に表すようになります）。
• ループ終了後、最後のウィンドウの一意な要素数を ans に追加します。
• ans を返します。

この方法では、各要素の追加・削除が O(1) で行えるため、全体の計算量は O(n) となり、毎回ウィンドウごとに集合を作り直す O(n×k) の素朴な実装よりもはるかに高速です。

Pythonでの実装例

from collections import Counter

class Solution:
    def solve(self, nums, k):
        # 最初のウィンドウの要素をカウント
        c = Counter()
        for i in range(k):
            c[nums[i]] += 1
        ans = []
        # ウィンドウを1つずつスライドさせながら処理
        for i in range(k, len(nums)):
            ans.append(len(c))          # 現在の一意な要素数を記録
            c[nums[i]] += 1             # 入ってくる要素を追加
            c[nums[i - k]] -= 1         # 出ていく要素を減らす
            if c[nums[i - k]] == 0:
                del c[nums[i - k]]      # カウント0なら辞書から削除
        ans.append(len(c))              # 最後のウィンドウ分を追加
        return ans

ob = Solution()
nums = [2, 2, 3, 3, 4]
print(ob.solve(nums, 2))

入力

[2, 2, 3, 3, 4], 2

出力

[1, 2, 1, 2]

まとめ

この実装のポイントは、collections.Counter を使って要素の出現頻度を管理し、カウントが 0 になった要素をこまめに辞書から削除することで、「辞書の長さ＝一意な要素数」という関係を常に保っている点です。これにより、大きなデータセットでも効率よくウィンドウごとのユニーク要素数を計算できます。