C++で0と1の個数が等しい最長の連続部分配列を求める方法

問題概要

0と1のみから構成されるバイナリ配列が与えられたとき、0と1の個数が等しい連続する部分配列(サブ配列)の最大長を求めることを考えます。

例えば、入力が [0,1,0] の場合、出力は 2 になります。[0,1] または [1,0] が、0と1の個数が等しい最長の連続部分配列だからです。

解法のアプローチ

この問題は「累積和」とハッシュマップを組み合わせることで効率的に解けます。1を +1、0を −1 として扱い、同じ累積和が2回現れた位置の間に、0と1の個数が等しい区間が存在すると考えるのがポイントです。

具体的な手順は以下の通りです。

• ret := 0(答え)、n := numsのサイズ、sum := 0(累積和)で初期化します。
• マップ m を作成し、m[0] := -1 を設定します(配列の先頭より前を表す番兵です)。
• i を 0 から numsのサイズ − 1 までループさせます。
  • nums[i] が 1 なら sum := sum + 1、そうでなければ sum := sum − 1 とします。
  • sum がすでにマップ m に存在する場合、ret := max(ret, i − m[sum]) で答えを更新します。存在しない場合は m[sum] := i として現在位置を記録します。
• 最後に ret を返します。

同じ累積和が再び現れたということは、その間の区間で +1 と −1 の加算が打ち消し合ったことになり、すなわち0と1の個数が等しいことを意味します。この手法により、計算量は O(n) と非常に効率的になります。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int findMaxLength(vector<int>& nums) {
        int ret = 0;
        int n = nums.size();
        int sum = 0;
        map <int, int> m;
        m[0] = -1;
        for(int i = 0; i < nums.size(); i++){
            sum += nums[i] == 1 ? 1: -1;
            if(m.count(sum)){
                ret = max(ret, i - m[sum]);
            }else m[sum] = i;
        }
        return ret;
    }
};
main(){
    vector<int> v = {0,1,0,0,1};
    Solution ob;
    cout << (ob.findMaxLength(v));
}

入力

[0,1,0,0,1]

出力

4

この例では、[0,1,0,0,1] の中で [0,1,0,1](インデックス0〜3)が0と1の個数が等しい最長の連続部分配列となるため、出力は 4 になります。