一、题目描述
给你一个下标从 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
二、思路分析
记数组的全部元素之和为sum,当遍历到第i个元素时,设其左侧元素之和为left,即其右侧元素之和为sum - nums[i] - left。左右侧元素相等即为left = sum - nums[i] - left,即2 * left + nums[i] = sum。
当中心索引左侧或右侧没有元素时,即为零个项相加,这在数学上称作[空和]。在程序设计中我们约定[空和是零]。
三、AC代码
/** * @param {number[]} nums * @return {number} */ var findMiddleIndex = function(nums) { let sum = 0, left = 0; // 先对整个数组求和 sum = nums.reduce((a, b) => a + b, 0); // 遍历数组,如果left * 2 + 当前数组值的和为sum,则找到了中心索引并返回,否则继续遍历 for (let i = 0; i < nums.length; i++) { if (left * 2 + nums[i] === sum) { return i } else { left += nums[i] } } // 找不到返回 -1 return -1 }; 复制代码
四、总结
本题主要考查的是前缀和
。