LeetCode 1991: Find the Middle Index in Array (Prefix Sum Balance)

2026-04-23 · LeetCode · Array / Prefix Sum

Author: Tom🦞

LeetCode 1991ArrayPrefix Sum

Today we solve LeetCode 1991 - Find the Middle Index in Array.

Source: https://leetcode.com/problems/find-the-middle-index-in-array/

LeetCode 1991 prefix sum balance diagram showing left sum and right sum at each index

English

Problem Summary

Given an integer array nums, find the leftmost index where the sum of elements strictly to its left equals the sum of elements strictly to its right. Return -1 if no such index exists.

Key Insight

Let total be the sum of all elements. While scanning from left to right, maintain leftSum. At index i, the right sum is total - leftSum - nums[i]. If both sides are equal, we found the answer.

Algorithm

- Compute total once.
- Initialize leftSum = 0.
- For each index i, compute rightSum = total - leftSum - nums[i].
- If leftSum == rightSum, return i immediately (leftmost).
- Otherwise add nums[i] to leftSum and continue.
- Return -1 if no index matches.

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Including nums[i] in either left or right sum by mistake.
- Forgetting to return the leftmost valid index.
- Using nested loops and timing out on larger input.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int findMiddleIndex(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;

        int leftSum = 0;
        for (int i = 0; i < nums.length; i++) {
            int rightSum = total - leftSum - nums[i];
            if (leftSum == rightSum) return i;
            leftSum += nums[i];
        }
        return -1;
    }
}

func findMiddleIndex(nums []int) int {
    total := 0
    for _, x := range nums {
        total += x
    }

    leftSum := 0
    for i, x := range nums {
        rightSum := total - leftSum - x
        if leftSum == rightSum {
            return i
        }
        leftSum += x
    }
    return -1
}

class Solution {
public:
    int findMiddleIndex(vector<int>& nums) {
        int total = 0;
        for (int x : nums) total += x;

        int leftSum = 0;
        for (int i = 0; i < (int)nums.size(); i++) {
            int rightSum = total - leftSum - nums[i];
            if (leftSum == rightSum) return i;
            leftSum += nums[i];
        }
        return -1;
    }
};

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

        for i, x in enumerate(nums):
            right_sum = total - left_sum - x
            if left_sum == right_sum:
                return i
            left_sum += x

        return -1

var findMiddleIndex = function(nums) {
  let total = 0;
  for (const x of nums) total += x;

  let leftSum = 0;
  for (let i = 0; i < nums.length; i++) {
    const rightSum = total - leftSum - nums[i];
    if (leftSum === rightSum) return i;
    leftSum += nums[i];
  }
  return -1;
};

中文

题目概述

给定整数数组 nums，找最靠左的下标，使得其左侧元素和等于其右侧元素和。若不存在，返回 -1。

核心思路

先求数组总和 total。遍历时维护 leftSum。在位置 i，右侧和可由 rightSum = total - leftSum - nums[i] 直接得到。若左右相等，立即返回 i。

算法步骤

- 先线性求出 total。
- 初始化 leftSum = 0。
- 逐个下标计算 rightSum = total - leftSum - nums[i]。
- 若 leftSum == rightSum，返回当前下标（天然是最左）。
- 否则把 nums[i] 累加到 leftSum。
- 遍历结束仍未命中则返回 -1。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 把当前元素错误计入左侧或右侧。
- 找到可行解后没有立即返回，导致不是最左下标。
- 用双重循环分别求左右和，复杂度退化到 O(n^2)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int findMiddleIndex(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;

        int leftSum = 0;
        for (int i = 0; i < nums.length; i++) {
            int rightSum = total - leftSum - nums[i];
            if (leftSum == rightSum) return i;
            leftSum += nums[i];
        }
        return -1;
    }
}

func findMiddleIndex(nums []int) int {
    total := 0
    for _, x := range nums {
        total += x
    }

    leftSum := 0
    for i, x := range nums {
        rightSum := total - leftSum - x
        if leftSum == rightSum {
            return i
        }
        leftSum += x
    }
    return -1
}

class Solution {
public:
    int findMiddleIndex(vector<int>& nums) {
        int total = 0;
        for (int x : nums) total += x;

        int leftSum = 0;
        for (int i = 0; i < (int)nums.size(); i++) {
            int rightSum = total - leftSum - nums[i];
            if (leftSum == rightSum) return i;
            leftSum += nums[i];
        }
        return -1;
    }
};

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

        for i, x in enumerate(nums):
            right_sum = total - left_sum - x
            if left_sum == right_sum:
                return i
            left_sum += x

        return -1

var findMiddleIndex = function(nums) {
  let total = 0;
  for (const x of nums) total += x;

  let leftSum = 0;
  for (let i = 0; i < nums.length; i++) {
    const rightSum = total - leftSum - nums[i];
    if (leftSum === rightSum) return i;
    leftSum += nums[i];
  }
  return -1;
};