Find Pivot Index
整数の配列 nums が与えられます。ピボットインデックスとは、その左側の値の合計と右側の値の合計が等しくなるインデックスです。ピボット自体の値はどちら側にも含まれず、値がない側の合計は 0 です。
最も左にあるピボットインデックスを返してください。ピボットとなるインデックスがない場合は、-1 を返してください。
関数
- numsinteger-array
- バランスを取る整数の配列
- 戻り値integer
- 最も左にあるピボットインデックス、存在しない場合は -1
制約
1 ≤ nums.length ≤ 104-1000 ≤ nums[i] ≤ 1000
例
- 入力
- nums = [3, 1, 5, 2, 2]
- 出力
- 2
- 説明
- インデックス 2 では、左側は 3 + 1 = 4、右側は 2 + 2 = 4 です。インデックス 0 とインデックス 1 では釣り合いません（左側 0 に対して右側 10、左側 3 に対して右側 9）。したがって、2 が最も左にあるピボットです。
- 入力
- nums = [1, 2, 3]
- 出力
- -1
- 説明
- 3つの候補は、それぞれ5に対して0、3に対して1、0に対して3を与えます。どのインデックスも釣り合わないので、答えは
-1です。
- 入力
- nums = [4, -4, 9]
- 出力
- 2
- 説明
- インデックス 2 では、左側は 4 + (-4) = 0 で、右側は空なので、合計も 0 です。最後のインデックスをピボットにできます。
提出時に隠しテスト+17件
発展問題
合計を先に求めずに、各値を一度だけ読み取って最も左のピボットを見つけられますか？その場合、メモリのコストはどれくらいですか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
1つのインデックスを確認するには、2つの合計が必要です。そのインデックスより前の値の合計と、後の値の合計です。各インデックスについて毎回それらを足し直すと、作業のほとんどが重複します。インデックス
iの2つの合計は、インデックスi+1の合計とどのように関係しているでしょうか？右に1歩進むと、左側の合計に
nums[i]が加わります。そして配列全体の合計が分かれば、左側の合計から右側の合計を求められます。つまり、全体の合計から左側の合計とnums[i]を引いたものです。まず配列全体の合計を求めます。次に、左から右へ、左側の合計を更新しながら進みます。各インデックスで、左側の合計と、合計から左側の合計および現在の値を引いた値を比較します。最初に一致したインデックスを返し、比較の後にのみ現在の値を左側の合計に加えます。ループが終了したら、-1 を返します。
解説
1つのインデックスを確認するには2つの合計を求めればよいですが、すべてのインデックスでそれらを再計算すると、処理量は長さの2乗に比例して増加します。解決策は、再計算をやめることです。左側の合計はステップごとに値が1つずつ増え、右側の合計は全体の合計から残りを差し引いたものです。合計を求めるパスと、左側の合計を更新しながら進む2回目のパスを使えば、メモリに2つの数値を保持するだけで、最も左にあるピボットを見つけられます。
各インデックスで両側を足し合わせる
正しいが、最大のテストでは終わらない
考え方
定義に従います。各インデックス i について、その前にある値を合計し、その後にある値を合計して、比較します。左から順にインデックスを試すため、2つの合計が一致する最初のインデックスが答えです。
端のケースは自然に処理できます。インデックス 0 では左側のループは0回実行されるため、左側の合計は0です。最後のインデックスでは右側のループが0回実行されます。そのため、[4, -4, 9] は 2 を返します。
問題は計算コストです。各インデックスで、ほかの n-1 個の値を合計するため、作業量は合計で約 n² 回の加算になります。値が10,000個の場合、加算回数は約1億回になり、その大部分は1つ前のインデックスですでに計算した合計を繰り返しています。
アルゴリズム
numsのすべてのインデックスについてiをループします。- 左側の合計として、
nums[0]からnums[i-1]までを合計します。 - 右側の合計として、
nums[i+1]から最後の値までを合計します。 - 2つの合計が等しければ、
iを返します。 - 一致するインデックスがなければ、-1 を返します。
def pivotIndex(nums):
n = len(nums)
for i in range(n):
left = 0
for j in range(i):
left += nums[j]
right = 0
for j in range(i + 1, n):
right += nums[j]
if left == right:
return i
return -1累積和配列
考え方
総当たり法では、配列の一連の要素を繰り返し加算します。累積和配列を使えば、その計算を一度で済ませられます。prefix[k]を先頭からk個の値の合計とし、prefix[0] = 0とします。[3, 1, 5, 2, 2]の場合、これは[0, 3, 4, 9, 11, 13]です。
これで、任意の一連の要素の合計は2つの要素の差で求められます。インデックスiの左側は先頭からi個の値なので、prefix[i]です。右側はnums[i]より後ろのすべての要素で、prefix[n] - prefix[i+1]です。インデックス2では、左側が4、右側が13 - 9 = 4となり、ピボットになります。
配列の構築には1回の走査が必要で、各チェックは定数時間で済むため、探索全体の計算量はO(n)です。その代わり、メモリ上に追加でn+1個の数値が必要です。
アルゴリズム
- 長さ
n+1のprefixを作成し、prefix[0] = 0とします。 - 値を設定します：
prefix[k+1] = prefix[k] + nums[k]。 - 各インデックス
iについて、左側の合計をprefix[i]、右側の合計をprefix[n] - prefix[i+1]として読み取ります。 - 左右の合計が等しくなる最初の
iを返します。ループ終了後も見つからなければ、-1を返します。
def pivotIndex(nums):
n = len(nums)
# prefix[k] is the sum of the first k values.
prefix = [0] * (n + 1)
for k in range(n):
prefix[k + 1] = prefix[k] + nums[k]
for i in range(n):
left = prefix[i]
right = prefix[n] - prefix[i + 1]
if left == right:
return i
return -1合計と左側の累積合計
考え方
前の方法でどのプレフィックスの要素を読み取るかを見てみましょう。インデックス i では、prefix[i]、prefix[i+1]、prefix[n] が必要です。最後の要素は合計で、変化することはありません。残りの2つは、配列を一度走査した場合の累積和です。したがって、配列全体を保持する代わりに、合計と左側の累積和だけを保持できます。
各値は左側、ピボット、右側のいずれかにあります。したがって、右側の合計は、合計から左側の合計と nums[i] を引いた値です。[3, 1, 5, 2, 2] の合計は13です。インデックス0では左側の合計は0、右側の合計は 13 - 0 - 3 = 10です。インデックス1では、左側が3、右側が9です。インデックス2では、左側が4、右側が 13 - 4 - 5 = 4なので、2を返します。
ループ内の順序が重要です。まず比較し、その後で nums[i] を左側の合計に加えます。そうすれば、左側の合計に検証中のインデックスの値が含まれることはありません。最初に一致した時点で返すことで、最も左のピボットが得られます。
配列を合計の計算と走査のために1回ずつ、合計2回読み取るので、時間計算量は O(n) です。保持する数値は2つだけなので、追加の空間計算量は O(1) です。
アルゴリズム
- すべての値を
totalに加算します。 leftを0に設定します。- 各インデックス
iについて、leftがtotal - left - nums[i]と等しい場合は、iを返します。 - そうでなければ、
nums[i]をleftに加算して次に進みます。 - ループが終了した場合は、-1を返します。
def pivotIndex(nums):
total = sum(nums)
left = 0
for i, value in enumerate(nums):
# Everything that is not on the left and not nums[i] is on the right.
if left == total - left - value:
return i
left += value
return -1
落とし穴と境界ケース
ほとんどの誤答は、ピボット自身の値をどちらか一方に含めるか、端のインデックスを飛ばしています。
- 比較の前に左側の合計に
nums[i]を加える。すると左側にピボットの値が含まれ、[3, 1, 5, 2, 2]ではインデックス 2 が見つからなくなります。 - 右側を
total - leftとして計算する。これでは右側にnums[i]が含まれるため、それも差し引いてください。 - インデックス 0 または最後のインデックスを飛ばす。片側が空なら合計は 0 になるため、どちらもピボットになり得ます。
[1, -1, 1]は 0 を返し、[4, -4, 9]は 2 を返します。 - 最初の一致ではなく、最後の一致を返す。
[0, 0, 0]ではすべてのインデックスで左右の合計が等しくなり、答えは 0 です。 - 両端から内側へ動かし、小さい方の側を大きくする2つのポインターを使う。これはすべての値が非負の場合にしか機能しません。ここでは値が -1000 まで下がるため、側を大きくしている途中で合計が小さくなることがあります。
- Lua と R の配列が 1 から始まることを忘れる。答えを 0 ベースのインデックスにするには、
i-1を返してください。
よくある質問4
Find Pivot Index の時間計算量は何ですか？
合計と累積和を使う解法は、O(n) 時間で実行できます。配列を合計するために1回走査し、さらに1回走査して調べます。追加の領域は O(1) です。代わりに、各インデックスで左右両側を再計算すると、O(n²) 時間がかかります。
なぜ右側の合計は、合計から左側とnums[i]を引いた値に等しいのでしょうか？
配列のすべての値は、iの左、iの位置、iの右の3か所のうち、ちょうど1か所にあります。それぞれの合計を足すと全体の合計になるため、右側の合計は、全体の合計からほかの2つの部分を引いた値になります。これにより、右側を合計しなくてもインデックスを確認できます。
Find Pivot Index は2つのポインターで解けますか？
確実とは言えません。小さい側を常に広げる2ポインター走査は、値を追加すると側の合計が大きくなることを前提としていますが、値が負になるとこの前提は成り立ちません。広げても側の合計が小さくなることがあるため、走査によってポインターが実際のピボットを通り過ぎる可能性があります。累積和を使う方法は値の符号を前提とせず、すべてのインデックスを確認します。
要素が 1 つの配列のピボットインデックスはいくつですか？
0です。唯一の要素の両側はどちらも空であり、空の側の合計は0なので、両側は等しくなります。累積和を使う解法では、最初の比較で0が返されます。左側は0で、合計から0と値を引いた結果も0です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def pivotIndex(nums):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
nums = [3, 1, 5, 2, 2]
期待値
2