C++で配列の平衡インデックスを求める方法を解説

問題の概要

この記事では、n個の整数値を含む配列 arr[] が与えられたとき、その平衡インデックス（equilibrium index）を見つけるプログラムをC++で作成する方法を解説します。

平衡インデックスとは、その位置より前にあるすべての要素の合計と、後ろにあるすべての要素の合計が等しくなるインデックスのことです。

サイズ n の配列 arr[] において、平衡インデックス e は次の条件を満たします。

sum(arr[0 … e-1]) = sum(arr[e+1 … n-1])

具体例で理解しよう

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

出力：3

説明：

インデックス3の要素「8」を基準にすると、左側と右側の要素の合計が一致します。

arr[0] + arr[1] + arr[2] = arr[4] + arr[5] + arr[6]

=> 5 + 1 + 2 = 3 + 4 + 1

=> 8 = 8

解法アプローチ①：素朴な方法（ネストしたループ）

最もシンプルなアプローチは、配列の各要素について「その要素が平衡インデックスになり得るか」を順番に確認していく方法です。

これにはネストしたループを使用します。外側のループで配列の各要素を走査し、内側のループでその要素の左側の合計（prevSum）と右側の合計（nextSum）をそれぞれ計算して比較します。両者が一致すれば、そのインデックスが平衡インデックスとなります。

この方法の計算量は O(n²) となるため、大きな配列では処理に時間がかかる点に注意が必要です。

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

例

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

int findEquilibriumIndex(int arr[], int n)
{
    int prevSum, nextSum;

    for (int i = 0; i < n; ++i) {

        prevSum = 0;
        for (int j = 0; j < i; j++)
            prevSum += arr[j];
        nextSum = 0;
        for (int j = i + 1; j < n; j++)
            nextSum += arr[j];

        if (prevSum == nextSum)
            return i;
    }
    return -1;
}

int main() {

    int arr[] = {5, 1, 2, 8, 3, 4, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"The equilibrium index is "<<findEquilibriumIndex(arr, n);
    return 0;
}

出力 −

The equilibrium index is 3

解法アプローチ②：累積和を使った O(n) の効率的な方法

配列全体の合計を事前に計算しておけば、各位置での右側の合計を「全体の合計 − 左側の合計 − 現在の要素」として即座に求められるため、O(n) の計算量で平衡インデックスを見つけられます。

手順は以下の通りです。

1. まず配列全体の合計 totalSum を計算します。
2. 配列を左から順に走査し、それまでの要素の合計 leftSum を管理します。
3. 各位置 i における右側の合計は rightSum = totalSum − leftSum − arr[i] で求めます。
4. leftSum == rightSum となれば、i が平衡インデックスです。

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

int findEquilibriumIndexOptimized(int arr[], int n)
{
    int totalSum = 0;
    for (int i = 0; i < n; i++)
        totalSum += arr[i];

    int leftSum = 0;
    for (int i = 0; i < n; i++) {
        int rightSum = totalSum - leftSum - arr[i];
        if (leftSum == rightSum)
            return i;
        leftSum += arr[i];
    }
    return -1;
}

int main() {
    int arr[] = {5, 1, 2, 8, 3, 4, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"The equilibrium index is "<<findEquilibriumIndexOptimized(arr, n);
    return 0;
}

出力 −

The equilibrium index is 3

まとめ

平衡インデックスを見つけるには、二重ループによる O(n²) の素朴な方法と、累積和を利用した O(n) の効率的な方法があります。どちらの実装でも、平衡インデックスが存在しない場合は -1 を返すようにしています。実務や競技プログラミングでは、計算量の観点から O(n) アプローチを採用するのが望ましいでしょう。