C++で指定された合計値を持つ部分配列を検索する方法（負の数への対応）

問題の概要

この問題では、ソートされていないN個の整数で構成される配列 arr[] が与えられます。求められているのは、指定された合計値に等しくなる部分配列（連続する要素の並び）を見つけることです。

具体例で問題を確認しましょう。

入力 : arr[] = {2, 5, -1, 4, 6, -9, 5}、合計 = 14
出力 : 部分配列 = {5, -1, 4, 6}

説明 −

部分配列の合計 = 5 + (-1) + 4 + 6 = 14

解法アプローチ1：二重ループによる全探索

最もシンプルな解法は、ネストされたループ（二重ループ）を使う方法です。外側のループで配列を走査し、内側のループで各開始位置から生成できるすべての部分配列を調べます。各部分配列について要素の合計を計算し、指定された合計値と比較します。一致すればその部分配列を出力し、配列全体を走査しても見つからなければ「該当する部分配列は存在しない」と出力します。

なお、合計が目標値を超えた時点で探索を打ち切る最適化は、配列に負の数が含まれると誤動作するため、この解法では使用していません。これにより負の数を含む配列でも正しく動作します。

アルゴリズム

• ステップ1 − 配列を i → 0 から (n-1) までループで走査します。

  • ステップ1.1 − 各要素を開始点として、可能なすべての部分配列の合計を求めます。

  • ステップ1.2 − 現在の部分配列の合計が指定された合計値と一致した場合、その部分配列を出力します。

• ステップ2 − 配列全体を走査しても部分配列が見つからなかった場合は、「指定された合計を持つ部分配列は見つかりませんでした！」と出力します。

コード例

この解法の動作を示すプログラムです。

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

void printSubArray(int arr[], int i, int j){
    cout << "{ ";
    for(; i < j; i++)
        cout << arr[i] << " ";
    cout << "}";
}

int findSubArrayWithSum(int arr[], int n, int sum) {
    int currSum;
    for (int i = 0; i < n; i++) {
        currSum = arr[i];
        for (int j = i + 1; j <= n; j++) {
            if (currSum == sum) {
                cout << "指定された合計を持つ部分配列 : ";
                printSubArray(arr, i, j);
                return 1;
            }
            if (j == n)
                break;
            currSum += arr[j];
        }
    }
    cout << "部分配列が見つかりません";
    return 0;
}

int main() {
    int arr[] = { 2, 5, -1, 4, 6, -9, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = 14;
    findSubArrayWithSum(arr, n, sum);
    return 0;
}

出力

指定された合計を持つ部分配列 : { 5 -1 4 6 }

この方法の時間計算量は O(n²) です。配列のサイズが大きくなると非効率になるため、より効率的なアプローチが求められます。

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

より優れたアプローチは、ハッシュマップ（unordered_map）を利用する方法です。ハッシュマップには、現在のインデックスまでの累積和（プレフィックスサム）とそのインデックスを格納していきます。各インデックスにおいて、「現在の累積和 − 目標の合計」と等しい累積和がすでに登場しているかを確認します。存在すれば、その直後の位置から現在の位置までの部分配列の合計が目標値に一致することを意味します。

この方法は負の数を含む配列でも正確に動作し、時間計算量は O(n) に抑えられます。

コード例

この解法の動作を示すプログラムです。

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

void printSubArray(int arr[], int i, int j){
    cout << "{ ";
    for(; i <= j; i++)
        cout << arr[i] << " ";
    cout << "}";
}

void findSubArrayWithSum(int arr[], int n, int sum) {
    unordered_map<int, int> map;
    int curr_sum = 0;
    for (int i = 0; i < n; i++){
        curr_sum = curr_sum + arr[i];
        if (curr_sum == sum) {
            cout << "指定された合計を持つ部分配列 : ";
            printSubArray(arr, 0, i);
            return;
        }
        if (map.find(curr_sum - sum) != map.end()) {
            cout << "指定された合計を持つ部分配列 : ";
            printSubArray(arr, map[curr_sum - sum] + 1, i);
            return;
        }
        map[curr_sum] = i;
    }
    cout << "部分配列が見つかりません！";
}

int main() {
    int arr[] = { 2, 5, -1, 4, 6, 9, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = 14;
    findSubArrayWithSum(arr, n, sum);
    return 0;
}

出力

指定された合計を持つ部分配列 : { 5 -1 4 6 }

まとめ

指定された合計値を持つ部分配列を検索する問題は、二重ループによる O(n²) の単純な解法と、累積和とハッシュマップを組み合わせた O(n) の効率的な解法の2通りで解くことができます。特に配列に負の数が含まれる場合は、ハッシュマップを使ったアプローチが確実かつ高速に動作するため推奨されます。