C++で解く合計配列パズル｜自身を除いた要素の総和を効率的に求める方法

配列（Array）とは

配列とは、同じデータ型の複数の要素をまとめて格納できるデータ構造です。複数の値を一度に扱えるのが大きな特徴ですが、その長さはあらかじめ定義しておく必要があります。

合計配列パズルとは

このパズルでは、サイズ n の配列 A1 が与えられます。これを解くために、配列 S1 を作成します。S1 には、対応する位置の要素を除いた A1 の全要素の合計を格納します。たとえば S1[3] を計算する場合、A1 の 4 番目の要素（インデックス 3）以外のすべての要素の合計を求めることになります。

具体例

配列 A1 = {1, 2, 3, 4, 6}
出力 S1 = {15, 14, 13, 12, 10}

解説 − 合計配列を求めるには、元の配列の各要素を合計変数に加算していきます。ただし、合計配列の同じ位置に対応する要素は除外します。つまり、合計配列の最初の要素を求める際には、配列の最初の要素を除いた残りの要素の合計を計算し、以降の要素も同様に処理します。このロジックに従って、合計配列の各要素の値を計算してみましょう。

Sum[0] では、インデックス 0 の要素を除いた要素の合計を計算します。

Sum[0] = 2 + 3 + 4 + 6 = 15

同様に sum[1] 以降の値も計算していきます。

Sum[1] = 1 + 3 + 4 + 6 = 14

Sum[2] = 1 + 2 + 4 + 6 = 13

Sum[3] = 1 + 2 + 3 + 6 = 12

Sum[4] = 1 + 2 + 3 + 4 = 10

これで合計配列のすべての要素が求まり、sum = {15, 14, 13, 12, 10} となります。

アルゴリズム

ステップ 1：元の配列のサイズを n とし、合計配列 sum[n] を 0 で初期化する。
ステップ 2：sum[] を反復処理しながら以下を行う。
　　ステップ 2.1：sum[i] に対して、j を 0 から n まで動かす for ループを実行する。
　　ステップ 2.2：if (i != j) { sum[i] += arr[j]; }
ステップ 3：標準出力を使って合計配列を表示する。

実装例

#include <iostream>
using namespace std;
int main() {
    int arr[] = { 3, 6, 4, 8, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int leftSum[n], rightSum[n], Sum[n], i, j;
    leftSum[0] = 0;
    rightSum[n - 1] = 0;
    cout << "元の配列 : \n";
    for (i = 0; i < n; i++)
        cout << arr[i] << " ";
    for (i = 1; i < n; i++)
        leftSum[i] = arr[i - 1] + leftSum[i - 1];
    for (j = n - 2; j >= 0; j--)
        rightSum[j] = arr[j + 1] + rightSum[j + 1];
    for (i = 0; i < n; i++)
        Sum[i] = leftSum[i] + rightSum[i];
    cout << "\n合計配列 : \n";
    for (i = 0; i < n; i++)
        cout << Sum[i] << " ";
    return 0;
}

出力結果

元の配列 :
3 6 4 8 9
合計配列 :
27 24 26 22 21

効率化のポイント

上記の実装では、単純な二重ループ（計算量 O(n²)）を使う代わりに、「左からの累積和（leftSum）」と「右からの累積和（rightSum）」を組み合わせています。leftSum[i] はインデックス i より前の要素の合計、rightSum[i] はインデックス i より後の要素の合計を表し、両者を加算することで、自身を除いた全要素の合計を O(n) の計算量で効率的に求められます。