题解 | #相等的草堆#

方法一（适用于无负数数组）：相向双指针。左边和小于右边和则左指针右移并加到左和，右边和小于左边和则右指针左移并加到右和，直到左右指针相遇。若相遇时左和仍然不等于右和，则失败，成功则返回指针。

#include <cstdio>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型
     */
    int pivotIndex(vector<int>& nums) {
        // write code here
        int len = nums.size();
        int left = 0, right = len - 1;
        int suml = nums[left], sumr = nums[right];
        while (left < right) {
            if (suml < sumr) {
                left++;
                suml += nums[left];
            } else if (suml > sumr) {
                right--;
                sumr += nums[right];
            } else {
                left++;
                right--;
                suml += nums[left];
                sumr += nums[right];
            }
        }
        if(suml==sumr)
            return left;
        else
         return -1;;
    }
};

方法二：从右边开始加的前缀和。把全局的前缀和先算出来，快速定区间。

#include <cstdio>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型
     */
    int pivotIndex(vector<int>& nums) {
        // write code here
        int len = nums.size();
        vector<int> sums(len + 1, 0);
        for (int i = len - 1; i >= 0; --i) {
            sums[i] = sums[i + 1] + nums[i];
        }

        // sum[i] : 前i个元素之和
        
        int val = 0;
        for (int i = 0; i < len; ++i) {
            if (val == sums[i + 1]) {
                return i;
            }
            val += nums[i];
        }
        return -1;
    }
};