C++で異なる整数がちょうどK個含まれる部分配列を数える方法

正の整数からなる配列Aがあるとします。連続する要素からなる部分配列（サブ配列）の中で、含まれる異なる整数の個数がちょうどK個であるものを「良い部分配列」と呼ぶことにします。例えば、配列 [1,2,3,1,2] には 1、2、3 という3つの異なる整数が含まれています。この記事では、配列Aに存在する「良い部分配列」の総数を求めるアルゴリズムを解説します。

問題の例

入力が [1,2,3,1,4]、K = 3 の場合を考えてみましょう。このとき出力は 4 になります。これは、異なる整数がちょうど3つ含まれる部分配列として、以下の4つが存在するためです。

• [1,2,3]
• [1,2,3,1]
• [2,3,1]
• [3,1,4]

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

この問題は「あと何個まで許容できるか」という考え方（At Most テクニック）を使うことで効率的に解けます。まず、異なる整数が最大k個まで含まれる部分配列の個数を数える関数 atMost(a, k) を定義します。

atMost() 関数の手順

• 配列 a と変数 k を受け取ります。
• 左端ポインタ j := 0、答え ans := 0、各整数の出現回数を記録するマップ m を用意します。
• 右端ポインタ i を0から順に進めます。
• 新しい要素 a[i] を追加し、まだ登録されていなければ k を減らします。
• k < 0 になったら（異なる整数が多すぎる場合）、条件を満たすまで左端 j を進めて窓を縮小します。要素が出現しなくなったら k を増やします。
• 各ステップで (i - j + 1) 個の部分配列が成立するので、これを ans に加算します。

最終的な答えは次の式で求められます。

atMost(a, k) - atMost(a, k - 1)

「最大k個」の場合から「最大k-1個」の場合を引くことで、ちょうどk個の異なる整数を含む部分配列だけを取り出せます。計算量はO(n)となり、非常に効率的です。

C++実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int subarraysWithKDistinct(vector<int>& a, int k) {
        return atMost(a, k) - atMost(a, k - 1);
    }
    int atMost(vector <int>& a, int k){
        set <int> current;
        int j = 0;
        int ans = 0;
        int n = a.size();
        unordered_map <int, int> m;
        for(int i = 0; i < a.size(); i++){
            if(!m[a[i]]++) k--;
            while(k < 0){
                if(!--m[a[j]])
                    k++;
                j++;
            }
            int x = ((i - j) + 1);
            ans += x;
        }
        return ans;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,2,3,1,4};
    cout << (ob.subarraysWithKDistinct(v, 3));
}

入力

{1,2,3,1,4}, 3

出力

4

この実装では、各要素が高々1回追加・削除されるため、全体の計算量はO(n)、空間計算量もO(n)で抑えられます。スライディングウィンドウと引き算テクニックの組み合わせは、「ちょうどK個」という条件を持つ部分配列問題における定番パターンなので、ぜひ覚えておきましょう。