LeetCode 题解工作台
左右元素和的差值
给你一个下标从 0 开始的长度为 n 的整数数组 nums 。 定义两个数组 leftSum 和 rightSum ，其中： leftSum[i] 是数组 nums 中下标 i 左侧元素之和。如果不存在对应的元素， leftSum[i] = 0 。 rightSum[i] 是数组 nums 中下标 …
2
题型
7
代码语言
3
相关题
当前训练重点
简单 · 前缀和
答案摘要
我们定义变量 表示数组 中下标 左侧元素之和，变量 表示数组 中下标 右侧元素之和。初始时 $l = 0$, $r = \sum_{i = 0}^{n - 1} \textit{nums}[i]$。 遍历数组 ，对于当前遍历到的数字 ，我们更新 $r = r - x$，此时 和 分别表示数组 中下标 左侧元素之和和右侧元素之和。我们将 和 的差的绝对值加入答案数组 中，然…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 前缀和 题型思路
题目描述
给你一个下标从 0 开始的长度为 n 的整数数组 nums。
定义两个数组 leftSum 和 rightSum，其中：
leftSum[i]是数组nums中下标i左侧元素之和。如果不存在对应的元素，leftSum[i] = 0。rightSum[i]是数组nums中下标i右侧元素之和。如果不存在对应的元素，rightSum[i] = 0。
返回长度为 n 数组 answer，其中 answer[i] = |leftSum[i] - rightSum[i]|。
示例 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 <= 10001 <= nums[i] <= 105
解题思路
方法一：前缀和
我们定义变量 表示数组 中下标 左侧元素之和，变量 表示数组 中下标 右侧元素之和。初始时 , 。
遍历数组 ，对于当前遍历到的数字 ，我们更新 ，此时 和 分别表示数组 中下标 左侧元素之和和右侧元素之和。我们将 和 的差的绝对值加入答案数组 中，然后更新 。
遍历结束，返回答案数组 即可。
时间复杂度 ，其中 是数组 的长度。空间复杂度 ，不考虑返回值的空间。
相似题目：
class Solution:
def leftRightDifference(self, nums: List[int]) -> List[int]:
l, r = 0, sum(nums)
ans = []
for x in nums:
r -= x
ans.append(abs(l - r))
l += x
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) due to single traversal for left and right sums. Space complexity is O(n) if separate arrays for leftSum and rightSum are maintained; it can be reduced to O(1) using in-place computation. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you know how to compute cumulative sums without nested loops?
- question_mark
Can you optimize to avoid recalculating sums for each index?
- question_mark
How would you reduce space usage if extra arrays are not allowed?
常见陷阱
外企场景- error
Forgetting that leftSum[i] excludes nums[i] itself, leading to off-by-one errors.
- error
Recomputing sums inside the loop, resulting in O(n^2) time instead of linear.
- error
Mixing up the direction for rightSum and computing it incorrectly.
进阶变体
外企场景- arrow_right_alt
Compute the difference between left and right product instead of sum for each index.
- arrow_right_alt
Find maximum absolute left-right sum difference instead of returning the full array.
- arrow_right_alt
Apply the same technique to a 2D matrix row-wise and column-wise for cumulative differences.