攻城獅
Not a programmer 不工程的攻城獅

Follow

Not a programmer 不工程的攻城獅

Follow

LeetCode Solution, Easy, 1991. Find the Middle Index in Array

在陣列中找出中間索引

攻城獅's photo
攻城獅
·Apr 26, 2022·
Play this article

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
    }
}

Did you find this article valuable?

Support 攻城獅 by becoming a sponsor. Any amount is appreciated!

Learn more about Hashnode Sponsors
 
Share this