【切图仔的算法修炼之旅】LeetCode1991:找到数组中的中间位置

简介: 【切图仔的算法修炼之旅】LeetCode1991:找到数组中的中间位置

一、题目描述


给你一个下标从 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
};
复制代码


四、总结


本题主要考查的是前缀和

相关文章
|
3月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
48 0
|
5月前
|
算法
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
|
2月前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
3月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
54 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
3月前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
36 2
|
3月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
27 4
|
3月前
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
31 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
|
3月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
26 0
Leetcode第三十三题(搜索旋转排序数组)
|
3月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
79 0
|
3月前
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
24 0