LeetCode 724. Find Pivot Index

Question

• https://leetcode.com/problems/find-pivot-index/

Given an array of integers nums, calculate the pivot index of this array.

The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right.

If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.

Return the leftmost pivot index. If no such index exists, return -1.

整数の配列numsが与えられたとき、この配列のpivot indexを計算する問題
pivot indexの定義を読むと「インデックスの左にあるすべての数の和が、インデックスの右にあるすべての数の和に等しくなるインデックスのこと」ということがわかる。
また、配列の範囲外は0とみなされるので、例えば[2,-1,1]などは右側の和が-1+1で、0番目がpivot indexとなる。
またpivot indexがないときは-1を返す

Code

class Solution {
    fun pivotIndex(nums: IntArray): Int {
        val numsSum = nums.sum()
        var leftSum = 0
        for (i in nums.indices) {
            if (leftSum == numsSum - leftSum - nums[i]) return i
            leftSum += nums[i]
        }
        return -1
    }
}

両端から中央方向まで足し合わせて、和が同値になったときなどと最初は考えていたが、
与えられる整数配列numsの和 - pivotより左側部分配列の和 - pivotより右側部分配列の和 - pivotのときの数 = 0という性質の中で、pivotより左側部分配列の和とpivotより右側部分配列の和が等しいことを利用すると leftSum == numsSum - leftSum - num[i]となるときのiを返せばpivotの値を求められる。

Profile

• Runtime: 236 ms
• Memory Usage: 45 MB

Submission

• https://leetcode.com/submissions/detail/593839893/