左右两边子数组和相等

给你一个整数数组 nums ，请计算数组的中心下标。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

  1. 如果中心下标位于最左端，那么左侧数之和视为0，因为在下标左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
  2. 如果数组有多个中心下标，应该返回最靠近左边的那一个。如果数组不存在中心下标返回-1

1.前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int ans = INT32_MAX;
        int len = nums.size();

        //1.初始化前缀和数组
        int *prefix = new int[len + 10]();
        for (int i = 1; i <= len; ++i) prefix[i] = prefix[i - 1] + nums[i - 1];

        //2.开始计算首先处理首位两种特殊情况
        if (prefix[len] - prefix[1] == 0) return 0;
        if (prefix[len - 1] == 0) ans = min(ans , len - 1);

        //3.处理一般情况
        for (int i = 1; i < len - 1; ++i) {
            if (prefix[i] == prefix[len] - prefix[i + 1])
                ans = min(ans, i);
        }
        return ans == INT32_MAX ? -1 : ans;
    }
};
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

2.前缀和优化

利用一些简单的数学知识知识，可以对前缀和的思路进行进一步的优化，

  1. 原思路：计算左右两边区间的和，再做判等比较，
  2. 优化后思路：计算左区间的区间和prefix，判断是否满足prefix*2 + nums[i] ?= sum ，这样也取消了边界值的特判操作。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int pivotIndex(vector<int> &nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int prefix = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (2 * prefix + nums[i] == sum) return i;
            prefix += nums[i];
        }
        return -1;
    }
};
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$