1991. 找到数组的中间位置
大约 2 分钟
---
1991. 找到数组的中间位置
- 标签:数组、前缀和
- 难度:简单
题目链接
题目大意
描述:给定一个下标从 开始的整数数组 。
要求:返回最左边的中间位置 (也就是所有可能中间位置下标做小的一个)。如果找不到这样的中间位置,则返回 。
说明:
- 中间位置 :满足 的数组下标。
- 如果 ,左边部分的和定义为 。类似的,如果 ,右边部分的和定义为 。
示例:
- 示例 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
解题思路
思路 1:前缀和
- 先遍历一遍数组,求出数组中全部元素和为 。
- 再遍历一遍数组,使用变量 为前 个元素和。
- 当遍历到第 个元素时,其数组左侧元素之和为 ,右侧元素和为 。
- 如果左右元素之和相等,即 () 时, 为中间位置。此时返回 。
- 如果不满足,则继续累加当前元素到 中,继续向后遍历。
- 如果找不到符合要求的中间位置,则返回 。
思路 1:代码
class Solution:
def findMiddleIndex(self, nums: List[int]) -> int:
total = sum(nums)
prefix_sum = 0
for i in range(len(nums)):
if 2 * prefix_sum + nums[i] == total:
return i
prefix_sum += nums[i]
return -1
思路 1:复杂度分析
- 时间复杂度:。
- 空间复杂度:。