《剑指 Offer》专项突破版 - 面试题 12 : 左右两边子数组的和相等（C++ 实现）

题目链接：LCR 012. 寻找数组的中心下标 - 力扣（LeetCode）

题目：

输入一个整数数组，如果一个数字左边的子数组的数字之和等于右边的子数组的数字之和，那么返回该数字的下标。如果存在多个这样的数字，则返回最左边一个数字的下标。如果不存在这样的数字，则返回 -1。例如，在数组 [1, 7, 3, 6, 2, 9] 中，下标为 3 的数字（值为 6）的左边 3 个数字 1、7、3 的和与右边 2 个数字 2 和 9 的和相等，都是 11，因此正确的输出值是 3。

分析：

这也是一道关于子数组的和的面试题。假设从头到尾扫描数组中的每个数字。当扫描到第 i 个数字时，它左边的数字之和就是从第 1 个数字累加到第 i - 1 个数字的和。此时它右边的子数组的数字之和就是从第 i + 1 个数字开始累加到最后一个数字的和，这个和等于数组中所有数字之和减去从第 1 个数字累加到第 i 个数字的和，因此需要先求数组中的所有数字之和。

代码实现：

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

时间复杂度为 O(n)，空间复杂度为 O(1)。