2574. 左右元素和的差值

Leetcode题目:前缀和

给你一个下标从 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] 。

示例 2:

输入:nums = [1]
输出:[0]
解释:数组 leftSum 为 [0] 且数组 rightSum 为 [0] 。
数组 answer 为 [|0 - 0|] = [0] 。

提示:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 105

解题思路

前缀和

如果直接照着题目写,那么分别计算两边的前缀和,完事。但感觉还是有点暴力,虽然时间复杂度是O(n)但是空间复杂度就比较麻烦。

class Solution {
public:
    vector<int> leftRightDifference(vector<int>& nums) {
        int size=nums.size();
        vector<int>leftSum;
        vector<int>rightSum;
        vector<int>answer;
        leftSum.resize(size);rightSum.resize(size);answer.resize(size);
        for(int i=1;i<size;i++)
        {
            leftSum[i]=leftSum[i-1]+nums[i-1];
        }
        for(int i=size-2;i>=0;i--)
        {
            rightSum[i]=rightSum[i+1]+nums[i+1];
        }
        for(int i=0;i<size;i++)
        {
            answer[i]=abs(leftSum[i]-rightSum[i]);
        }
        return answer;
    }
};

Subscribe
提醒
0 评论
Inline Feedbacks
View all comments
0
在此留下你的评论x