【算法|前缀和系列No.3】leetcode LCR 012. 寻找数组的中心下标

╰+攻爆jí腚メ 2024-04-27 06:38 69阅读 0赞

> 个人主页：[兜里有颗棉花糖][Link 1]  
> 欢迎 点赞? 收藏✨ 留言✉ 加关注?本文由 [兜里有颗棉花糖][Link 1] 原创  
> 收录于专栏【[手撕算法系列专栏][Link 2]】【[leetcode][])】  
> ?本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助  
> ?希望我们一起努力、成长，共同进步。  
> ![在这里插入图片描述][503fbf94852e4752a15da4b418a9909c.png]

[点击直接跳转到该题目][Link 3]

#### 目录 ####

*  1️⃣题目描述
 *  2️⃣题目解析
 *  3️⃣解题代码

## 1️⃣题目描述 ##

给你一个整数数组 `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 <=  1 0 4 10^\{4\} 104
 *  `-1000 <= nums[i] <= 1000`

## 2️⃣题目解析 ##

前缀和数组`l[i]`，表示下标为`i`的元素左边元素之和  
后缀和数组`r[i]`，表示下标为`i`的元素右边元素之和

**状态转移方程：**

*  `l[i] = l[i - 1] + nums[i]`
 *  `r[i] = r[i + 1] + nums[i + 1`

**最后注意本题目的初始化问题，以防造成越界访问。**

## 3️⃣解题代码 ##

class Solution {
        
    public:
        int pivotIndex(vector<int>& nums) {
        
            int n = nums.size();
            vector<int> l(n),r(n);
            r[n - 1] = 0;
            for(int i = 1;i < n;i++) l[i] = l[i - 1] + nums[i - 1];
            for(int i = n - 2;i >= 0;i--) r[i] = r[i + 1] + nums[i + 1];
            for(int i = 0;i < n;i++)
            {
        
                if(l[i] == r[i]) return i;
            }
            return -1;
        }
    };

**最后就是通过啦！！！**  
![在这里插入图片描述][cb155b34301b469d8067353bad3529d9.png]

[Link 1]: https://xiaofeizhu.blog.csdn.net/
[Link 2]: https://blog.csdn.net/m0_74352571/category_12364106.html
[leetcode]: https://blog.csdn.net/m0_74352571/category_12252087.html
[503fbf94852e4752a15da4b418a9909c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/30beadbe6f7c484e99fe13a10b1b2086.png
[Link 3]: https://leetcode.cn/problems/tvdfij/description/
[cb155b34301b469d8067353bad3529d9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/b0c1f7804327405fb268e07d146e7c07.png