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

### Did you find this article valuable?

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