本文共 827 字,大约阅读时间需要 2 分钟。
为了解决这个问题,我们需要找到数组的“中心索引”。中心索引的定义是左侧所有元素的和等于右侧所有元素的和。如果有多个满足条件的索引,返回最靠近左边的那个。如果不存在这样的索引,返回-1。
这种方法的时间复杂度是O(n),其中n是数组的长度。我们先计算总和,然后再遍历一次数组,确保在最优时间复杂度内解决问题。
#include#include // for accumulateusing namespace std;int pivotIndex(vector & nums) { int sum_total = accumulate(nums.begin(), nums.end(), 0); int sum_left = 0; for (int i = 0; i < nums.size(); ++i) { if (2 * sum_left + nums[i] == sum_total) { return i; } sum_left += nums[i]; } return -1;}
accumulate
函数计算数组所有元素的总和。这种方法确保了在最优时间复杂度内找到中心索引,适用于大数组的情况。
转载地址:http://ntkj.baihongyu.com/