JavaScriptでシャーロック配列の問題を解く方法｜左右の合計が等しい要素を見つける

ワトソンはシャーロックに長さNの配列Aを渡します。そして、「その配列の中に、ある要素を基準としたとき左側の要素の合計と右側の要素の合計が等しくなるような要素が存在するかどうか」を判定するよう求めます。

今回はこの問題をJavaScriptの関数として実装します。関数は数値の配列を受け取り、条件を満たす要素が存在すればそのインデックスを返し、存在しない場合は-1を返します。

アルゴリズムの考え方

この問題を効率よく解くカギとなるのは、配列全体の合計値を先に計算しておくことです。あとは配列を先頭から順に走査しながら、次の手順を繰り返します。

• 合計値から現在の要素を引く → 残った値が右側の合計になる
• その値とこれまでの左側の合計（leftSum）を比較する
• 両者が一致すれば、そのインデックスを返す
• 一致しなければ、現在の要素をleftSumに加算して次の要素へ進む

この方法なら配列を一度だけ走査すればよいため、時間計算量はO(N)と非常に効率的です。

コード例

const arr = [1, 2, 3, 4, 5, 7, 3];
const arr2 = [4, 6, 3, 4, 5, 2, 1];
const isSherlockArray = arr => {
    let sum = arr.reduce((acc, val) => acc + val);
    let leftSum = 0;
    for(let i = 0; i < arr.length; i++){
        sum -= arr[i];
        if(sum === leftSum){
            return i;
        };
        leftSum += arr[i];
    };
    return -1;
};
console.log(isSherlockArray(arr));
console.log(isSherlockArray(arr2));

出力結果

コンソールには次のように表示されます。

4
-1

動作の解説

例1：[1, 2, 3, 4, 5, 7, 3] の場合、インデックス4（値は5）の位置で、左側の合計（1+2+3+4=10）と右側の合計（7+3=10）が一致するため、4が返されます。

例2：[4, 6, 3, 4, 5, 2, 1] の場合、どの要素を基準にしても左右の合計が一致しないため、-1が返されます。