Given a 0-indexed integer array nums, find a 0-indexed integer array answer where:
answer.length == nums.length.
answer[i] = |leftSum[i] - rightSum[i]|.
Where:
leftSum[i] is the sum of elements to the left of the index i in the array nums. If there is no such element, leftSum[i] = 0.
rightSum[i] is the sum of elements to the right of the index i in the array nums. If there is no such element, rightSum[i] = 0.
Return the array answer.
Example 1:
Input: nums = [10,4,8,3]
Output: [15,1,11,22]
Explanation: The array leftSum is [0,10,14,22] and the array rightSum is [15,11,3,0].
The array answer is [|0 - 15|,|10 - 11|,|14 - 3|,|22 - 0|] = [15,1,11,22].
Example 2:
Input: nums = [1]
Output: [0]
Explanation: The array leftSum is [0] and the array rightSum is [0].
The array answer is [|0 - 0|] = [0].
Constraints:
1 <= nums.length <= 1000
1 <= nums[i] <= 105
左右元素和的差值。
给你一个下标从 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 。
思路是前缀和，这里我提供两种实现，一种用了额外空间，另一种不需要额外空间。
需要额外空间的做法是创建两个和input数组等长的数组，记录 leftsum 和 rightsum。当遍历到nums[i] 的时候，我们就可以以O(1)的时间得到这个元素左边所有元素的和以及这个元素右边所有元素的和。
时间O(n)
空间O(n)
Java实现
class Solution {
public int[] leftRightDifference(int[] nums) {
int[] leftSum = new int[n];
leftSum[0] = 0;
for (int i = 1; i < n; i++) {
leftSum[i] = leftSum[i - 1] + nums[i - 1];
}
int[] rightSum = new int[n];
rightSum[n - 1] = 0;
for (int i = n - 2; i >= 0; i--) {
rightSum[i] = rightSum[i + 1] + nums[i + 1];
}
int[] res = new int[n];
for (int i = 0; i < n; i++) {
res[i] = Math.abs(leftSum[i] - rightSum[i]);
}
return res;
}
}
再来是不用额外空间的做法。首先我用一个变量 total 计算一下整个数组所有元素的累加和。接着我们再次从左往右遍历 input 数组，此时我再用另一个变量 leftSum 记录从左往右所有元素的累加和。当我遍历到 num[i] 的时候，此时我有了 leftSum，num[i]，那么在这个位置右边所有元素的累加和 rightSum = total - nums[i] - leftSum。通过这个办法我就可以得到每个下标位置上的 leftSum 和 rightSum。
时间O(n)
空间O(1)
Java实现
class Solution {
public int[] leftRightDifference(int[] nums) {
int total = 0;
for (int num : nums) {
total += num;
}
int n = nums.length;
int leftSum = 0;
int[] res = new int[n];
res[0] = total - nums[0];
res[n - 1] = total - nums[n - 1];
for (int i = 1; i < n - 1; i++) {
leftSum += nums[i - 1];
int rightSum = total - nums[i] - leftSum;
res[i] = Math.abs(leftSum - rightSum);
}
return res;
}
}