题目描述

给定一个整数类型的数组 nums,请编写一个能够返回数组“中心索引”的方法。

我们是这样定义数组中心索引的:数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。

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

示例一

输入: 
nums = [1, 7, 3, 6, 5, 6]
输出: 3
解释:
索引3 (nums[3] = 6) 的左侧数之和(1 + 7 + 3 = 11),与右侧数之和(5 + 6 = 11)相等。
同时, 3 也是第一个符合要求的中心索引。

示例二

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

说明

  • nums 的长度范围为 [0, 10000]
  • 任何一个 nums[i] 将会是一个范围在 [-1000, 1000]的整数。

题目分析

思路一(延迟2000ms+)

  1. 思路迭代数组,判断每一个数左边数之和是否等于右边数之和
  2. 需要一个大循环套两个小循环,时间复杂度以及空间复杂度较高
  3. 注意当数组元素为一、为二时等特殊情况,注意竞赛时多次提交会罚时!

思路二(延迟28ms+)

  1. 首先直接计算所有数组元素之和
  2. 之后从数组下标为零开始,依次减去该数组元素值,累加到之前减去的数值,并判断被减去后的值是否等于减数的值
  3. 该方法不用考虑什么特殊情况

参考代码

思路一

class Solution {
public:
int pivotIndex(vector<int>& nums) {
int len = nums.size();
//当数组长度为一时,0一定时中心索引
if(len == 1) return 0 ;
//当数组长度为二且第二个元素为0时,0一定是中心索引,否则一定不存在中心索引
if(len == 2){
if(nums[1] == 0) {return 0;}
else {return -1 ;}
}
for(int i = 0; i < len ; i++)
{
int left = 0 , right = accumulate(nums.begin() + i + 1 , nums.end(),0);
if(i == 0) {left = 0;}
else {left = accumulate(nums.begin() , nums.begin()+i,0);}
if(left == right) {return i ;}
}
return - 1;
}
};

思路二

class Solution {
public:
int pivotIndex(vector<int>& nums) {
int size = nums.size(),i = 0 , tatal = 0 ,left = 0;
for (i=0;i<size;i++) {total += nums[i];}

for (i=0;i<size;i++) {
if (total-nums[i] == 2*left) {return i;}
left += nums[i];
}
return -1;
}
};

总结

竞赛题需要思考,涉及问题等价转换(及建模)。如果按照题目要求按部就班的做,一般时复杂繁琐的或者无法用过的。

谢谢访问