Easy

题目描述

给你一个下标从 0 开始的整数数组 nums，请你找到 最左边 的中间位置 middleIndex（也就是所有可能中间位置下标中最小的一个）。

中间位置 middleIndex 是满足 nums[0] + nums[1] + ... + nums[middleIndex-1] == nums[middleIndex+1] + nums[middleIndex+2] + ... + nums[nums.length-1] 的数组下标。

如果 middleIndex == 0，左边部分的和为 0。类似地，如果 middleIndex == nums.length - 1，右边部分的和为 0。

请你返回满足上述条件 最左边 的 middleIndex，如果不存在这样的中间位置，请你返回 -1。

示例 1：

输入：nums = [2,3,-1,8,4]
输出：3
解释：
下标 3 之前的数字和：2 + 3 + (-1) = 4
下标 3 之后的数字和：4 = 4

示例 2：

输入：nums = [1,-1,4]
输出：2
解释：
下标 2 之前的数字和：1 + (-1) = 0
下标 2 之后的数字和：0

示例 3：

输入：nums = [2,5]
输出：-1
解释：不存在符合要求的 middleIndex。

提示：

  • 1 <= nums.length <= 100
  • -1000 <= nums[i] <= 1000

**注意：**本题与第 724 题相同：https://leetcode-cn.com/problems/find-pivot-index/

解题思路

解题思路

这道题要求找到数组中的"中间索引"，使得该索引左边所有元素的和等于右边所有元素的和。

方法一：前缀和（推荐）

核心思想是利用前缀和来快速计算左右两边的和：

  1. 先计算数组的总和 total
  2. 从左到右遍历数组，维护左边的和 leftSum
  3. 对于当前索引 i，右边的和 = total - leftSum - nums[i]
  4. 如果左边的和等于右边的和，返回当前索引
  5. 更新 leftSum 继续下一次循环

这种方法只需要一次遍历，时间复杂度为 O(n)，空间复杂度为 O(1)。

方法二：朴素解法

对于每个索引，分别计算左边和右边的和，然后比较。这种方法的时间复杂度为 O(n²)，虽然简单但效率较低。

由于题目数据规模不大（n ≤ 100），两种方法都可以通过，但推荐使用前缀和方法，因为它更高效且是最优解。

代码实现

class Solution {
public:
    int findMiddleIndex(vector<int>& nums) {
        int total = 0;
        for (int num : nums) {
            total += num;
        }
        
        int leftSum = 0;
        for (int i = 0; i < 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 in range(len(nums)):
            right_sum = total - left_sum - nums[i]
            if left_sum == right_sum:
                return i
            left_sum += nums[i]
        
        return -1

public class Solution {
    public int FindMiddleIndex(int[] nums) {
        int total = nums.Sum();
        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;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMiddleIndex = function(nums) {
    const totalSum = nums.reduce((sum, num) => sum + num, 0);
    let leftSum = 0;
    
    for (let i = 0; i < nums.length; i++) {
        let rightSum = totalSum - leftSum - nums[i];
        if (leftSum === rightSum) {
            return i;
        }
        leftSum += nums[i];
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
前缀和O(n)O(1)
朴素解法O(n²)O(1)

其中 n 为数组长度。推荐使用前缀和解法，它只需要遍历数组两次（一次计算总和，一次找中间索引），空间复杂度为常数级别。

相关题目