C++で配列のすべての一意な部分配列の合計値の総和を求める方法

この記事では、n個の整数からなる配列 arr[] が与えられたときに、一意な(重複しない)部分配列の合計値をすべて集め、その総和を求める方法をC++で解説します。ここでいう「部分配列の合計」とは、ある部分配列に含まれる全要素を足し合わせた値のことです。

問題の確認

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

入力: arr[] = {1, 2, 4}
出力: 23

解説:

配列のすべての部分配列は次のとおりです:
(1), (2), (4), (1, 2), (2, 4), (1, 2, 4)
部分配列の合計 = 1 + 2 + 4 + (1+2) + (2+4) + (1+2+4) = 23

解法1: ソートを利用するアプローチ

基本的な考え方は、すべての部分配列の合計値を一旦ベクトルに格納し、ソートすることで重複する値を見つけ出すというものです。その後、一意な値だけを合計に加算します。

アルゴリズムの手順

1. ステップ1: すべての部分配列の合計を求め、vectorに格納します。
2. ステップ2: vectorをソートします。
3. ステップ3: 隣接する要素を比較し、重複する値をすべて0に置き換えます(一意な値のみ残す)。
4. ステップ4: 合計を計算して出力します。

実装例

以下のプログラムは、この解法の動作を示したものです。

#include <bits/stdc++.h>
using namespace std;
long int findSumOfSubArraySum(int arr[], int n){
    int i, j;
    long int sumArrayTill[n + 1] = { 0 };
    for (i = 0; i < n; i++)
        sumArrayTill[i + 1] = sumArrayTill[i] + arr[i];
    vector<long int> subArraySum;
    for (i = 1; i <= n; i++)
        for (j = i; j <= n; j++)
            subArraySum.push_back(sumArrayTill[j] - sumArrayTill[i - 1]);
    sort(subArraySum.begin(), subArraySum.end());
    for (i = 0; i < subArraySum.size() - 1; i++){
        if (subArraySum[i] == subArraySum[i + 1]) {
            j = i + 1;
            while (subArraySum[j] == subArraySum[i] && j < subArraySum.size()){
                subArraySum[j] = 0; j++;
            }
            subArraySum[i] = 0;
        }
    }
    long sum = 0;
    for (i = 0; i < subArraySum.size(); i++)
        sum += subArraySum[i];
    return sum;
}
int main(){
   int arr[] = { 1, 2, 4, 7, 9 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The sum of all unique subarray sum is "<<findSumOfSubArraySum(arr, n);
   return 0;
}

出力

The sum of all unique subarray sum is 144

この方法では、部分配列の列挙にO(n²)、ソートにO(n² log n)の計算量が必要となるため、全体の時間計算量はO(n² log n)となります。

解法2: ハッシュテーブルを利用するアプローチ

より効率的な方法として、ハッシュテーブル(unordered_map)を使う方法があります。各部分配列の合計値をキーとしてハッシュマップに記録し、出現回数をカウントしていきます。最後に、出現回数がちょうど1回の(つまり一意な)部分配列の合計値だけを足し合わせます。

実装例

以下のプログラムは、この解法の動作を示したものです。

#include <bits/stdc++.h>
using namespace std;
long int findSumOfSubArraySum(int arr[], int n){
    int sumSubArraySum = 0;
    unordered_map<int, int> sumSubArray;
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {
            sum += arr[j];
            sumSubArray[sum]++;
        }
    }
    for (auto itr : sumSubArray)
        if (itr.second == 1)
            sumSubArraySum += itr.first;
        return sumSubArraySum;
}
int main(){
   int arr[] = { 1, 2, 4, 7, 5 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The sum of all unique subarray sum is "<<findSumOfSubArraySum(arr, n);
   return 0;
}

出力

The sum of all unique subarray sum is 124

ハッシュテーブルを利用することでソート処理が不要になり、平均時間計算量はO(n²)に改善されます。

まとめ

配列のすべての一意な部分配列の合計値の総和を求める問題では、ソートによる重複除去と、ハッシュマップによる出現回数のカウントという2つのアプローチが有効です。特にハッシュマップを使う方法は、ソートを省略できるため、大規模な配列に対してより効率的に動作します。用途やデータサイズに応じて、適切な手法を選択しましょう。