C++で配列内を移動した後の左ポインタのインデックスを求める方法

この問題では、サイズNの配列arr[]が与えられ、配列内で可能な移動を行った後の左ポインタのインデックスを求めることが課題となります。

配列には2つのポインタ、すなわち左ポインタと右ポインタが用意されています。

左ポインタはインデックス0から開始し、値は増加していきます。

右ポインタはインデックス(n-1)から開始し、値は減少していきます。

ポインタの値は、通過した合計値がもう一方より小さい場合に増加します。つまり、左ポインタの合計が右ポインタの合計より小さければ左ポインタが増加し、そうでなければ右ポインタが減少します。そして合計値は更新されます。

問題を理解するための例

入力 : arr[] = {5, 6, 3, 7, 9, 4}
出力 : 2

説明 −

leftPointer = 0 -> 合計 = 5, rightPointer = 5 -> 合計 = 4. 右ポインタを移動
leftPointer = 0 -> 合計 = 5, rightPointer = 4 -> 合計 = 13. 左ポインタを移動
leftPointer = 1 -> 合計 = 11, rightPointer = 4 -> 合計 = 13. 左ポインタを移動
leftPointer = 2 -> 合計 = 14, rightPointer = 4 -> 合計 = 13. 右ポインタを移動
leftPointer = 2 -> 合計 = 14, rightPointer = 3 -> 合計 = 20. 右ポインタを移動
左ポインタの位置は 2 となります。

解決アプローチ

この問題のシンプルな解決方法は、合計値に基づいて左ポインタと右ポインタを移動させることです。そして、左ポインタが右ポインタより1つ大きくなったかどうかを確認します。

実装例

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

#include <iostream>
using namespace std;
int findIndexLeftPointer(int arr[], int n) {
   if(n == 1)
      return 0;
   int leftPointer = 0,rightPointer = n-1,leftPointerSum = arr[0], rightPointerSum = arr[n-1];
   while (rightPointer > leftPointer + 1) {
      if (leftPointerSum < rightPointerSum) {
         leftPointer++;
         leftPointerSum += arr[leftPointer];
      }
      else if (leftPointerSum > rightPointerSum) {
         rightPointer--;
         rightPointerSum += arr[rightPointer];
      }
      else {
         break;
      }
   }
   return leftPointer;
}
int main() {
   int arr[] = { 5, 6, 3, 7, 9, 4 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"移動後の左ポインタのインデックスは "<<findIndexLeftPointer(arr, n);
   return 0;
}

出力

移動後の左ポインタのインデックスは 2

このアルゴリズムの時間計算量はO(N)であり、各要素は最大で1回ずつ訪問されるため、効率的な解法となっています。両ポインタが交差するか隣接するまで、合計値の比較に基づいて移動を繰り返すことで、最終的な左ポインタの位置を求めることができます。