计算数组中心位置 华为od真题 100
时间: 2023-05-08 20:01:29 浏览: 76
题目描述
给定一个整数数组nums,编写一个函数来计算它的中心位置。中心位置可以按如下方式定义:在位置i之前的所有元素的和等于位置i之后的所有元素的和。如果不存在这样的位置,则应该返回-1。如果有多个中心位置,那么应该返回最左边的那个。
例如:输入:nums=[1,7,3,6,5,6],输出:3,解释:中心位置在索引3,前面元素的和相加(1 + 7 + 3 = 11),后面元素的和相加(5 + 6 = 11)。
思路分析
可以创建一个变量来储存数组的总和,再顺序遍历这个数组,每次从总和中减去当前位置的值,并将总和减去当前位置的值和当前位置的值相比较,如果相等,则当前位置就是中心位置。
代码实现
int pivotIndex(int* nums, int numsSize){
int sum = 0, leftsum = 0;
for (int i = 0; i < numsSize; ++i) {
sum += nums[i];
}
for (int i = 0; i < numsSize; ++i) {
if (leftsum == sum - leftsum - nums[i]) {
return i;
}
leftsum += nums[i];
}
return -1;
}
时间复杂度:O(n)
空间复杂度:O(1)
结语
本题主要是通过一个变量来储存数组的总和,顺序遍历这个数组,并在遍历到每个元素时更新左半部分的和,最后判断左侧和右侧之和是否相等。
这道题的思路比较简单,但是边界条件需要注意。