刷爆力扣之寻找数组的中心下标

简介: 刷爆力扣之寻找数组的中心下标

一 🏠 题目描述

724. 寻找数组的中心下标


给你一个整数数组 nums ,请计算数组的 中心下标


数组 中心下标 是数组的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和。


如果中心下标位于数组最左端,那么左侧数之和视为 0 ,因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用


如果数组有多个中心下标,应该返回 最靠近左边 的那一个。如果数组不存在中心下标,返回 -1


示例 1:

输入:nums = [1, 7, 3, 6, 5, 6]
输出:3
解释:
中心下标是 3左侧数之和 sum = nums[0] + nums[1] + nums[2] =1+7+3=11右侧数之和 sum = nums[4] + nums[5] =5+6=11 ,二者相等。

示例 2:


输入:nums = [1, 2, 3]
输出:-1
解释:
数组中不存在满足此条件的中心下标。

示例 3:

输入:nums = [2, 1, -1]
输出:0
解释:
中心下标是 0左侧数之和 sum =0 ,(下标 0 左侧不存在元素),
右侧数之和 sum = nums[1] + nums[2] =1+-1=0


提示:


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


二 🏠破题思路

2.1 🚀 关键信息

解决问题第一步,当然先提取题目字面上的关键信息 😎😎😎


数组 中心下标 是数组的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和



从题干易知,sum - nums[i] = pivotIndexLeftSum + pivotIndexRightSum =2 * pivotIndexLeftSum


提取完题目中的关键信息后,直接进入第二阶段,思路整理 😃😃😃



2.2 🚀 思路整理

一次遍历


遍历数组,当满足 sum ==2 * pivotIndexLeftSum + nums[i] 时,返回索引



整理完解题思路后,直接进入第三阶段,代码实现 😃😃😃



三 🏠 代码详解

3.1 🚀 代码实现

按照我们刚才的破题思路,直接代码走起来 👇👇👇👇


int pivotIndex(vector<int>& nums) {
    int pivotIndexLeftSum =0, len = nums.size(); //初始化左侧之和, 获取数组长度
    int sum = accumulate(nums.begin(), nums.end(), 0); //计算数字总和
for (int i =0; i < len; ++i) { //遍历数组
if (sum ==2 * pivotIndexLeftSum + nums[i]) return i; //满足条件, 则返回索引
        pivotIndexLeftSum += nums[i]; //否则将当前值加入左侧之和, 移动索引
    }
    return -1; //返回 -1}



3.2 🚀 细节解析

看完 👀👀👀 全注释版的代码实现后,相信看官大大对整体逻辑已经是大写的 OK 了 😃😃😃


那么我们挖一 🏠 题目描述

724. 寻找数组的中心下标


给你一个整数数组 nums ,请计算数组的 中心下标


数组 中心下标 是数组的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和。


如果中心下标位于数组最左端,那么左侧数之和视为 0 ,因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用


如果数组有多个中心下标,应该返回 最靠近左边 的那一个。如果数组不存在中心下标,返回 -1


示例 1:


输入:nums = [1, 7, 3, 6, 5, 6]
输出:3
解释:
中心下标是 3左侧数之和 sum = nums[0] + nums[1] + nums[2] =1+7+3=11右侧数之和 sum = nums[4] + nums[5] =5+6=11 ,二者相等。

示例 2:


输入:nums = [1, 2, 3]
输出:-1
解释:
数组中不存在满足此条件的中心下标。

示例 3:


输入:nums = [2, 1, -1]
输出:0
解释:
中心下标是 0左侧数之和 sum =0 ,(下标 0 左侧不存在元素),
右侧数之和 sum = nums[1] + nums[2] =1+-1=0

提示:


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

二 🏠破题思路

2.1 🚀 关键信息

解决问题第一步,当然先提取题目字面上的关键信息 😎😎😎


数组 中心下标 是数组的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和



从题干易知,sum - nums[i] = pivotIndexLeftSum + pivotIndexRightSum =2 * pivotIndexLeftSum


提取完题目中的关键信息后,直接进入第二阶段,思路整理 😃😃😃



2.2 🚀 思路整理

一次遍历


遍历数组,当满足 sum == 2 * pivotIndexLeftSum + nums[i] 时,返回索引



整理完解题思路后,直接进入第三阶段,代码实现 😃😃😃



三 🏠 代码详解

3.1 🚀 代码实现

按照我们刚才的破题思路,直接代码走起来 👇👇👇👇


int pivotIndex(vector<int>& nums) {
    int pivotIndexLeftSum =0, len = nums.size(); //初始化左侧之和, 获取数组长度
    int sum = accumulate(nums.begin(), nums.end(), 0); //计算数字总和
for (int i =0; i < len; ++i) { //遍历数组
if (sum ==2 * pivotIndexLeftSum + nums[i]) return i; //满足条件, 则返回索引
        pivotIndexLeftSum += nums[i]; //否则将当前值加入左侧之和, 移动索引
    }
    return -1; //返回 -1}


3.2 🚀 细节解析

看完 👀👀👀 全注释版的代码实现后,相信看官大大对整体逻辑已经是大写的 OK 了 😃😃😃


那么我们挖掘上述实现的晦涩细节 😖😖😖 进行解析,直接开干,走起来 👇👇👇👇



if (sum ==2 * pivotIndexLeftSum + nums[i]) 

很直白的题,无特殊点,核心是左侧所有元素相加和等于右侧所有元素相加和 🐳🐳🐳



四 🏠 心路历程

为方便各位看官大大了解博主真实刷题过程,我把当时状态纯纯真实还原,记录在心路历程这一小节,不感兴趣的小伙伴可以直接跳过哈


博主在第一阶段提取 🚀 关键信息没有问题,在第二阶段 🚀 思路整理没有问题 (上述实现和题解博主原创)


相关文章
|
1月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
38 0
|
3月前
|
算法
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
LeetCode------找到所有数组中消失的数字(6)【数组】
这篇文章介绍了LeetCode上的"找到所有数组中消失的数字"问题,提供了一种解法,通过两次遍历来找出所有未在数组中出现的数字:第一次遍历将数组中的每个数字对应位置的值增加数组长度,第二次遍历找出所有未被增加的数字,即缺失的数字。
|
1月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
19 4
|
1月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
18 0
Leetcode第三十三题(搜索旋转排序数组)
|
1月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
56 0
|
1月前
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
16 0
|
3月前
|
算法
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
|
3月前
|
算法 索引
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
这篇文章介绍了LeetCode第34题"在排序数组中查找元素的第一个和最后一个位置"的解题方法,通过使用双指针法从数组两端向中间同时查找目标值,有效地找到了目标值的首次和最后一次出现的索引位置。
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
|
3月前
|
算法
LeetCode第33题搜索旋转排序数组
这篇文章介绍了LeetCode第33题"搜索旋转排序数组"的解题方法,通过使用二分查找法并根据数组的有序性质调整搜索范围,实现了时间复杂度为O(log n)的高效搜索算法。
LeetCode第33题搜索旋转排序数组