C++で合計が0となるすべての部分配列を出力する方法

この記事では、整数値の配列が与えられたときに、要素の合計が0になるすべての部分配列（連続した要素の並び）を見つけ出し、それらを出力する方法をC++で解説します。

問題の概要

まず、具体例を使って問題を理解しましょう。

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

この配列の場合、合計が0になる部分配列は以下の通りです。

• {0} … インデックス1のみ
• {-5, 0, 2, 3} … インデックス0〜3
• {3, -3} … インデックス3〜4
• {-3, 4, -1} … インデックス4〜6
• {-5, 0, 2, 3, -3, 4, -1} … インデックス0〜6（配列全体）

アプローチ1: すべての部分配列を調べる全探索

最も直感的な解法は、取り得るすべての部分配列について合計を計算し、0になるものを出力するというものです。この方法は理解しやすい一方で、二重ループが必要となるため時間計算量はO(n^2)となり、配列サイズが大きい場合には非効率になります。

アプローチ2: ハッシュマップを使った効率的な解法

より優れた手法が「累積和」と「ハッシュマップ」を組み合わせる方法です。左から順に累積和を計算していき、同じ累積和が2回現れたとき、その2つの位置の間にある部分配列の合計は必ず0になります。この性質を利用すれば、配列を一度走査するだけで答えを求められます。

アルゴリズムの手順

1. 累積和を格納する変数 sum を用意します。
2. sum が0になった場合、インデックス0から現在の位置までの部分配列が条件を満たします。
3. 現在の sum がハッシュマップに登録済みかどうかを確認します。
4. 登録済みの場合、記録されていた位置の次のインデックスから現在位置までの部分配列の合計は0になります。
5. 未登録の場合は、現在の sum とインデックスをハッシュマップに追加します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
vector< pair<int, int> > findSubArrayWithSumZero(int arr[], int n){
    unordered_map<int, vector<int> > map;
    vector< pair<int, int> > out;
    int sum = 0;
    for (int i = 0; i < n; i++){
        sum += arr[i];
        if (sum == 0)
            out.push_back(make_pair(0, i));
        if (map.find(sum) != map.end()){
            vector<int> vc = map[sum];
            for (auto it = vc.begin(); it != vc.end(); it++)
                out.push_back(make_pair(*it + 1, i));
        }
        map[sum].push_back(i);
    }
    return out;
}
int main(){
    int arr[] = {-5, 0, 2, 3, -3, 4, -1};
    int n = sizeof(arr)/sizeof(arr[0]);
    vector<pair<int, int> > out = findSubArrayWithSumZero(arr, n);
    if (out.size() == 0)
        cout << "No subarray exists";
    else
        for (auto it = out.begin(); it != out.end(); it++)
            cout << "Subarray with sum 0 is from " << it->first << " to " << it->second << endl;
    return 0;
}

このコードでは、unordered_map のキーに累積和を、値にその累積和が出現したインデックスのリストを格納しています。同じ累積和が複数回現れた場合にも対応できるよう、各インデックスを vector で管理している点がポイントです。

実行結果

Subarray with sum 0 is from 1 to 1
Subarray with sum 0 is from 0 to 3
Subarray with sum 0 is from 3 to 4
Subarray with sum 0 is from 0 to 6
Subarray with sum 0 is from 4 to 6

出力は「開始インデックス から 終了インデックス まで」という形式で、合計が0になる部分配列がすべて列挙されています。該当する部分配列がひとつも存在しない場合は、「No subarray exists」と表示されます。

計算量の目安

• 時間計算量: 配列を一度だけ走査するため O(n)。ただし、条件を満たす部分配列の個数が多い場合は、その出力分のコストが加わります。
• 空間計算量: ハッシュマップに累積和を保存するため O(n)。

まとめ

合計が0になる部分配列の検出は、累積和とハッシュマップを組み合わせることで、全探索よりも大幅に効率化できます。「同じ累積和が再び現れた区間の合計は0になる」という性質は、他の配列問題にも応用できる重要なテクニックなので、ぜひ覚えておきましょう。