找到数组的中间位置

难度: 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 。

示例 4：

输入：nums = [1]
输出：0
解释：
下标 0 之前的数字和为：0
下标 0 之后的数字和为：0

提示：

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

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

Submission

运行时间: 18 ms

内存: 16.0 MB

class Solution:
    def findMiddleIndex(self, nums: List[int]) -> int:
        s = []
        prev = 0
        for i in nums:
            prev += i
            s.append(prev)
        for i in range(len(nums)):
            if s[i] - nums[i] == s[-1] - s[i]:
                return i
        return -1

Explain

这道题目要求找到数组中的一个中间位置middleIndex，使得该位置左侧所有元素的和等于右侧所有元素的和。解题思路是首先计算数组的前缀和，并存储在数组s中。每个前缀和s[i]代表从数组开始到第i个元素的总和。之后，遍历数组并检查每个位置i，如果位置i左侧的元素总和等于右侧的元素总和，那么这个位置就是中间位置。这可以通过比较s[i] - nums[i]（移除位置i的元素后的左侧和）和s[-1] - s[i]（从i到数组末尾的和）是否相等来判断。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def findMiddleIndex(self, nums: List[int]) -> int:
        s = []  # 存储前缀和
        prev = 0  # 前缀和的累计变量
        for i in nums:  # 计算前缀和
            prev += i
            s.append(prev)
        for i in range(len(nums)):  # 检查每个索引是否可以是middleIndex
            if s[i] - nums[i] == s[-1] - s[i]:  # 比较左侧和与右侧和是否相等
                return i  # 找到符合条件的索引，返回
        return -1  # 如果没有找到符合条件的索引，返回-1

Explore

在计算前缀和的过程中，数组s的初始值为空是为了方便从第一个元素开始累加。这样做允许在遍历nums数组时，逐步构建前缀和数组s。如果从nums的第一个元素开始，我们需要在循环之前设置特殊的初始条件，这可能会使代码更加复杂并增加出错的可能。通过从空数组开始，并在每次迭代中添加当前的累积总和，我们可以保持代码的简洁性和一致性。

在这个算法中，s[i]表示从数组开头到第i个元素的累计和（包括第i个元素本身）。因此，s[i] - nums[i]实际上计算的是从数组开头到第i个元素之前的总和，即位置i左侧的元素和。另一方面，s[-1]是整个数组的总和，s[-1] - s[i]则计算的是从第i+1个元素到数组末尾的总和，即位置i右侧的元素和。通过比较这两个值，我们可以判断位置i左右两边的和是否相等，从而确定是否为中间位置。

包含负数或零的元素不会影响前缀和的计算方法，因为前缀和只是简单地累加数组中的每个元素。不过，负数或零的存在会影响累加的总值，可能导致前缀和在某些点增加、减少或保持不变。这种变化会直接影响中间位置的检测逻辑，因为我们需要找到一个点，其左侧的元素总和等于右侧的元素总和。含负数或零的数组在逻辑上处理方式相同，关键在于正确计算并比较左右两侧的和。

是的，该算法在遇到多个可能的中间位置时，总是返回最左边的那一个。这是因为算法从数组的第一个元素开始向右遍历，并在找到第一个使左右两侧和相等的索引时立即返回该索引。因此，如果数组中有多个符合条件的中间位置，算法会停在最左边的那一个并返回，不会继续检查后面的元素。