leetcode LCR 012.寻找数组的中心下标

一、题目描述

二、解题思路

整体思路：

由于题目要求的是两个连续区间的和，所以可以使用前缀和来解决这个问题。

具体思路：

(1)首先进行边界处理，如果数组为空，则直接返回-1；

(2)构造前缀和数组，注意这个数组是从下标0开始，dp[0]要单独处理一下；

(3)使用前缀和数组，计算ptr两侧的子数组的和，如果相等，则返回ptr。若dp数组遍历完毕也未找到中心下标，则返回-1。

三、代码实现

时间复杂度：T(n)=O(n)

空间复杂度：S(n)=O(n)

class Solution {
public:int pivotIndex(vector<int>& nums) {//边界处理if(nums.empty()) return -1;//构造前缀和数组vector<int> dp(nums.size(),0);dp[0]=nums[0];for(int i=1;i!=dp.size();i++) dp[i]=dp[i-1]+nums[i];//使用前缀和数组for(int ptr=0;ptr!=dp.size();ptr++){if(dp[ptr]-nums[ptr]==dp[dp.size()-1]-dp[ptr])return ptr;}return -1;}
};