C++で左側の配列の合計と右側の配列の合計が等しくなる要素を配列内から検索する方法

問題の概要

n個の要素を持つ配列Aがあるとします。この課題は、配列Aを2つの部分配列に分割したときに、それぞれの部分配列の要素の合計が等しくなるような分割点の要素を見つけることです。

例えば、配列A = [2, 3, 4, 1, 4, 5]の場合、答えは「1」となります。要素1を境界として、左側の部分配列は[2, 3, 4]、右側の部分配列は[4, 5]となり、両者の合計はどちらも9で一致します。

解法のアプローチ

この問題は、累積和を利用することで時間計算量O(n)・空間計算量O(1)という高い効率で解くことができます。手順は以下のとおりです。

まず、配列の最初の要素を除いた残りの要素すべての合計をright_sumとして計算します。この時点では、最初の要素が分割候補の要素とみなされます。

次に、配列を左から右へ走査していきます。各ステップで、right_sumから要素を1つ減算し、left_sumに要素を1つ加算します。そして、right_sumとleft_sumが等しくなる点を探します。その点が、求めている分割要素となります。

もし配列全体を走査しても等しくなる点が見つからない場合は、-1を返してそのような分割が存在しないことを示します。

サンプルコード

#include<iostream>
using namespace std;
int getPartitionElement(int arr[], int size) {
   int right = 0, left = 0;
   for (int i = 1; i < size; i++)
      right += arr[i];
      for (int i = 0, j = 1; j < size; i++, j++) {
         right -= arr[j];
         left += arr[i];
         if (left == right)
            return arr[i + 1];
      }
   return -1;
}
int main() {
   int arr[] = { 2, 3, 4, 1, 4, 5 };
   int size = sizeof(arr) / sizeof(arr[0]);
   cout << "Partition element: " << getPartitionElement(arr, size);
}

実行結果

Partition element: 1