1991. 找到数组的中间位置
1991. 找到数组的中间位置
题目
Given a 0-indexed integer array nums
, find the leftmostmiddleIndex
(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. Find Pivot Index.
题目大意
给你一个下标从 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. 寻找数组的中心下标题解 相同。
解题思路
在数组中,找到一个数,使得它左边的数之和等于它的右边的数之和,如果存在,则返回这个数的下标索引,否作返回 -1
。
这里面存在一个等式,只需要满足这个等式即可满足条件:leftSum + num[i] = sum - leftSum
=> 2 * leftSum + num[i] = sum
。
- 总和计算:先计算数组的总和
total
,然后通过逐步累加leftSum
(左侧元素和),检查当前索引是否满足中心索引的条件,即2 * leftSum + nums[i] === total
。 - 如果找到这样的索引,返回其值;如果找不到,返回
-1
。 - 题目提到如果存在多个索引,则返回最左边那个,因此从左开始求和,而不是从右边。
复杂度分析
- 时间复杂度:
O(n)
,其中n
是数组nums
的长度。- 总和计算使用
reduce
方法遍历数组求和,时间复杂度为O(n)
; - 在主循环中,遍历数组每个元素,通过检查和更新
leftSum
判断是否满足条件,这个操作也是线性的O(n)
。
- 总和计算使用
- 空间复杂度:
O(1)
,使用了常数级别的额外空间。
代码
/**
* @param {number[]} nums
* @return {number}
*/
var findMiddleIndex = function (nums) {
const total = nums.reduce((acc, cur) => acc + cur, 0);
let leftSum = 0;
for (let i = 0; i < nums.length; i++) {
if (2 * leftSum + nums[i] == total) return i;
leftSum += nums[i];
}
return -1;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
724 | 寻找数组的中心下标 | [✓] | 数组 前缀和 | 🟢 | 🀄️ 🔗 |
1013 | 将数组分成和相等的三个部分 | [✓] | 贪心 数组 | 🟢 | 🀄️ 🔗 |
2219 | 数组的最大总分 🔒 | 数组 前缀和 | 🟠 | 🀄️ 🔗 | |
2270 | 分割数组的方案数 | 数组 前缀和 | 🟠 | 🀄️ 🔗 | |
2574 | 左右元素和的差值 | 数组 前缀和 | 🟢 | 🀄️ 🔗 |