Follow

Follow

·Apr 26, 2022·

# 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].

## 解法解析

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