1991. Find the Middle Index in Array

題目敘述

Given a 0-indexed integer array nums, find the leftmost middleIndex (i.e., the smallest amongst all the possible ones).

A middleIndex is an index where nums[0] + nums[1] + ... + nums[middleIndex-1] == nums[middleIndex+1] + nums[middleIndex+2] + ... + nums[nums.length-1].

If middleIndex == 0, the left side sum is considered to be 0. Similarly, if middleIndex == nums.length - 1, the right side sum is considered to be 0.

Return the leftmost middleIndex that satisfies the condition, or -1 if there is no such index.

Example 1:

Input: nums = [2,3,-1,8,4]
Output: 3
Explanation: The sum of the numbers before index 3 is: 2 + 3 + -1 = 4
The sum of the numbers after index 3 is: 4 = 4

Example 2:

Input: nums = [1,-1,4]
Output: 2
Explanation: The sum of the numbers before index 2 is: 1 + -1 = 0
The sum of the numbers after index 2 is: 0

Example 3:

Input: nums = [2,5]
Output: -1
Explanation: There is no valid middleIndex.

Constraints:

• 1 <= nums.length <= 100
• -1000 <= nums[i] <= 1000

Note: This question is the same as 724: https://leetcode.com/problems/find-pivot-index/

Hint 1:

Could we go from left to right and check to see if an index is a middle index?

Hint 2:

Do we need to sum every number to the left and right of an index each time?

Hint 3:

Use a prefix sum array where prefix[i] = nums[0] + nums[1] + ... + nums[i].

題目翻譯

這題是需要再陣列 nums 中找出中間值的索引，其中這個中間值需要滿足的條件是。其中間值的左右兩側各自加總相同。

解法解析

這題有許多解法，有些程式語言有內建的函數可以使用，會讓寫法更簡單。這邊有個簡單的算式，假設全部元素的加總是 sum，左側的加總是 left，右側是 right。

left = right - nums[i]
left = (sum - left) - nums[i]
left * 2 = sum - nums[i]

解法範例

Go

func findMiddleIndex(nums []int) int {
    var (
        left  int
        right int
    )
    for _, val := range nums {
        right += val
    }

    for i, val := range nums {
        right -= val
        if left == right {
            return i
        }
        left += val
    }
    return -1
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMiddleIndex = function (nums) {
    let left = 0,
        right = nums.reduce((a, b) => a + b, 0);
    for (let i = 0; i < nums.length; i++) {
        right -= nums[i];
        if (left === right) {
            return i;
        }
        left += nums[i];
    }
    return -1;
};

Kotlin

Kotlin 的 withIndex 可以遍歷的同時也附帶索引

class Solution {
    fun findMiddleIndex(nums: IntArray): Int {
        var left = 0
        var right = nums.sum()
        for ((i, value) in nums.withIndex()) {
            right -= value
            if (left == right) {
                return i
            }
            left += value
        }
        return -1
    }
}

PHP

PHP 可以使用 array_sum 直接加總

class Solution
{

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function findMiddleIndex($nums)
    {
        $left = 0;
        $right = array_sum($nums);
        foreach ($nums as $i => $value) {
            $right -= $value;
            if ($left == $right) {
                return $i;
            }
            $left += $value;
        }

        return -1;
    }
}

Python

class Solution:
    def findMiddleIndex(self, nums: List[int]) -> int:
        left = 0
        right = sum(nums)

        for i in range(len(nums)):
            right -= nums[i]
            if left == right:
                return i
            left += nums[i]

        return -1

Rust

impl Solution {
    pub fn find_middle_index(nums: Vec<i32>) -> i32 {
        let right = nums.iter().sum::<i32>();
        let mut left = 0;

        for (idx, num) in nums.iter().enumerate() {
            match right - left - num == left {
                true => return idx as i32,
                false => left += num,
            }
        }
        -1
    }
}

Swift

class Solution {
    func findMiddleIndex(_ nums: [Int]) -> Int {
        var left = 0
        var right = nums.reduce(0, +)
        for (i, val) in nums.enumerated() {
            right -= nums[i]
            if left == right {
                return i
            }
            left += nums[i]
        }
        return -1
    }
}