LeetCode 2574. 左右元素和的差值_左右连续的差值

给你一个下标从 0 开始的整数数组 nums ，请你找出一个下标从 0 开始的整数数组 answer ，其中：

answer.length == nums.length
answer[i] = |leftSum[i] - rightSum[i]|
其中：

leftSum[i] 是数组 nums 中下标 i 左侧元素之和。如果不存在对应的元素，leftSum[i] = 0 。
rightSum[i] 是数组 nums 中下标 i 右侧元素之和。如果不存在对应的元素，rightSum[i] = 0 。
返回数组 answer 。

示例 1：

输入：nums = [10,4,8,3]
输出：[15,1,11,22]
解释：数组 leftSum 为 [0,10,14,22] 且数组 rightSum 为 [15,11,3,0] 。
数组 answer 为 [|0 - 15|,|10 - 11|,|14 - 3|,|22 - 0|] = [15,1,11,22] 。

解法一：先计算出leftSum和rightSum，然后模拟即可：

class Solution {
public:
    vector<int> leftRigthDifference(vector<int>& nums) {
        int sz = nums.size();
        vector<int> leftSum(sz);
        leftSum[0] = 0;
        for (int i = 1; i < sz; ++i) {
            leftSum[i] = nums[i - 1] + leftSum[i - 1];
        }

        vector<int> rightSum(sz);
        rightSum[sz - 1] = 0;
        for (int i = sz - 2; i >= 0; --i) {
            rightSum[i] = nums[i + 1] + rightSum[i + 1];
        }

        vector<int> ans(sz);
        for (int i = 0; i < sz; ++i) {
            ans[i] = abs(leftSum[i] - rightSum[i]);
        }

        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

如果输入数组大小为n，此算法时间复杂度为O（n），空间复杂度为O（n）。

解法二：可以边遍历边计算leftSum和rightSum的当前和，从而减少空间复杂度：

class Solution {
public:
    vector<int> leftRigthDifference(vector<int>& nums) {
        int rightSum = accumulate(nums.begin(), nums.end(), 0);
        int leftSum = 0;
        int sz = nums.size();
        vector<int> ans(sz);
        for (int i = 0; i < sz; ++i) {
            rightSum -= nums[i];
            ans[i] = abs(leftSum - rightSum);
            leftSum += nums[i];
        }

        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

如果输入数组大小为n，此算法时间复杂度为O（n），空间复杂度为O（1）。