局域网站建设银行信用卡,百度代理,营销推广计划,蓝田县住房与城乡建设局网站给你一个下标从 0 开始的整数数组 nums #xff0c;请你找出一个下标从 0 开始的整数数组 answer #xff0c;其中#xff1a;
answer.length nums.length answer[i] |leftSum[i] - rightSum[i]| 其中#xff1a;
leftSum[i] 是数组 nums 中下标 i 左侧元素之和。如果不…给你一个下标从 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:vectorint leftRigthDifference(vectorint nums) {int sz nums.size();vectorint leftSum(sz);leftSum[0] 0;for (int i 1; i sz; i) {leftSum[i] nums[i - 1] leftSum[i - 1];}vectorint rightSum(sz);rightSum[sz - 1] 0;for (int i sz - 2; i 0; --i) {rightSum[i] nums[i 1] rightSum[i 1];}vectorint ans(sz);for (int i 0; i sz; i) {ans[i] abs(leftSum[i] - rightSum[i]);}return ans;}
};如果输入数组大小为n此算法时间复杂度为On空间复杂度为On。
解法二可以边遍历边计算leftSum和rightSum的当前和从而减少空间复杂度
class Solution {
public:vectorint leftRigthDifference(vectorint nums) {int rightSum accumulate(nums.begin(), nums.end(), 0);int leftSum 0;int sz nums.size();vectorint ans(sz);for (int i 0; i sz; i) {rightSum - nums[i];ans[i] abs(leftSum - rightSum);leftSum nums[i];}return ans;}
};如果输入数组大小为n此算法时间复杂度为On空间复杂度为O1。
