LeetCode - 寻找数组的中心

先学习一下前缀和吧

LCR 012. 寻找数组的中心下标

代码解析

在读题读到左侧元素之和等于右侧所有元素之和的时候，我觉得可以用前缀和，然后结合下面的示例，模拟了一下发现确实可以。

我的想法是搞两个数组，一个来存从左到右数组中的前缀和，另一个来存从右到左数组中的前缀和。然后在一个for循环中去判断两个前缀和数组的值是否相等就可以了。

学C++的小伙伴在用vector初始话的时候，要记得，从右到左的vector容量要比原数组大2。

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        vector<int> lsum(n + 1, 0);
        vector<int> rsum(n + 2, 0); // 只大1会越界，画个图想一想为什么

        for (int i = 1,j = n; i <= n; i++,j--)
        {
            lsum[i] = lsum[i - 1] + nums[i - 1];
            rsum[j] = rsum[j + 1] + nums[j - 1]; // 越界与这里有关
        }

        for (int i = 1; i <= n; i++)
        {
            if (lsum[i] == rsum[i]) return i - 1;
        }
        return -1;

    }
};

我写完之后又看了一下官方的解法，发现，比我写的好多了，用的前缀和 + 简单推理。

class Solution {
public:
    int pivotIndex(vector<int> &nums) {
        int total = accumulate(nums.begin(), nums.end(), 0);
        int sum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (2 * sum + nums[i] == total) {
                return i;
            }
            sum += nums[i];
        }
        return -1;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/tvdfij/solutions/1038043/zuo-you-liang-bian-zi-shu-zu-de-he-xiang-5j4r/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。