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

# [1991. Find the Middle Index in Array](https://leetcode.com/problems/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

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

```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` 可以遍歷的同時也附帶索引

```kotlin
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` 直接加總

```php
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

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

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

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