C++で合計が0となる部分配列の存在を効率的に判定する方法

はじめに

この記事では、整数値からなるサイズ n の配列 arr[] が与えられたときに、合計が0となる部分配列（サブアレイ）が存在するかどうかを判定する方法を解説します。

具体的には、配列の中に「すべての要素の合計が0に等しい」連続した部分配列が含まれているかどうかを確認する問題です。

問題の例

入力： arr[] = {3, 1, -2, 1, 4, 5}

出力： Yes

説明：

部分配列 {1, -2, 1} の要素の合計は 1 + (-2) + 1 = 0 となり、条件を満たしています。このため答えは「Yes」となります。

解法アプローチ

1. 素朴な解法（全探索）

最もシンプルな方法は、考えられるすべての部分配列を列挙し、それぞれの要素の合計が0になるかどうかを確認することです。しかし、この方法では時間計算量が O(n²) になり、配列のサイズが大きくなると非効率です。

2. ハッシュを使った効率的な解法

より効率的なのがハッシング（ハッシュテーブル）を活用する方法です。このアイデアは「累積和（プレフィックスサム）」の性質に基づいています。

アルゴリズムの手順は以下の通りです。

• 配列を先頭から走査し、現在のインデックスまでの累積和を計算します。
• 同じ累積和が過去に出現している場合、その間の部分配列の合計は必ず0になります。
• また、累積和自体が0になった場合も、先頭からの部分配列の合計が0であることを意味します。
• 上記のどちらかに該当すれば true を返し、最後まで見つからなければ false を返します。

この手法を使えば、時間計算量 O(n)、空間計算量 O(n) で問題を解くことができます。

C++での実装例

#include <bits/stdc++.h>
using namespace std;

bool isSubArraySumZero(int arr[], int n) {
    
    unordered_set<int> sumHash;

    int currSum = 0;
    for (int i = 0 ; i < n ; i++) {
        
        currSum += arr[i];
        if (currSum == 0 || sumHash.find(currSum) != sumHash.end())
            return true;
        sumHash.insert(currSum);
    }
    return false;
}

int main() {
    
    int arr[] = { 3, 1, -2, 1, 4, 5 };
    int n = sizeof(arr)/sizeof(arr[0]);
    if (isSubArraySumZero(arr, n))
        cout<<"SubArray with sum equal to 0 exists in the array";
    else
        cout<<"No subarray exists";
    return 0;
}

出力結果

SubArray with sum equal to 0 exists in the array

まとめ

合計が0となる部分配列の存在確認は、累積和とハッシュセットを組み合わせることで線形時間で解決できます。ポイントは「同じ累積和が二度現れたら、その間の部分配列の合計は必ず0になる」という性質です。全探索による O(n²) の素朴な解法と比べて大幅に高速化できるため、実務やコーディング面接でも役立つテクニックとして覚えておきましょう。