Easy

题目描述

给你一个下标从 0 开始的整数数组 nums，数组大小为 n。

定义两个数组 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 <= 1000
  • 1 <= nums[i] <= 10^5

解题思路

这是一道典型的前缀和问题。我们需要计算每个位置左侧元素的和与右侧元素的和，然后求它们的绝对差值。

方法一：暴力解法

最直观的方法是对每个位置 i，分别计算其左侧和右侧所有元素的和。时间复杂度为 O(n²)。

方法二：前缀和优化（推荐）

我们可以先计算出整个数组的总和，然后通过一次遍历同时计算左侧和与右侧和：

  • 对于位置 i，左侧和就是前缀和
  • 右侧和 = 总和 - 左侧和 - nums[i]

具体步骤：

  1. 计算数组总和 totalSum
  2. 遍历数组，维护左侧和 leftSum
  3. 对于每个位置 i：
    • 右侧和 rightSum = totalSum - leftSum - nums[i]
    • 计算 |leftSum - rightSum|
    • 更新 leftSum += nums[i] 为下一次迭代准备

这种方法只需要一次遍历，时间复杂度为 O(n)，空间复杂度为 O(1)（不包括返回数组）。

代码实现

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

class Solution:
    def leftRightDifference(self, nums: List[int]) -> List[int]:
        n = len(nums)
        total_sum = sum(nums)
        
        answer = []
        left_sum = 0
        
        for i in range(n):
            right_sum = total_sum - left_sum - nums[i]
            answer.append(abs(left_sum - right_sum))
            left_sum += nums[i]
        
        return answer

public class Solution {
    public int[] LeftRightDifference(int[] nums) {
        int n = nums.Length;
        int[] answer = new int[n];
        
        int totalSum = 0;
        foreach (int num in nums) {
            totalSum += num;
        }
        
        int leftSum = 0;
        for (int i = 0; i < n; i++) {
            int rightSum = totalSum - leftSum - nums[i];
            answer[i] = Math.Abs(leftSum - rightSum);
            leftSum += nums[i];
        }
        
        return answer;
    }
}

var leftRightDifference = function(nums) {
    const n = nums.length;
    const answer = new Array(n);
    
    const totalSum = nums.reduce((sum, num) => sum + num, 0);
    
    let leftSum = 0;
    for (let i = 0; i < n; i++) {
        const rightSum = totalSum - leftSum - nums[i];
        answer[i] = Math.abs(leftSum - rightSum);
        leftSum += nums[i];
    }
    
    return answer;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)
空间复杂度O(1)

其中 n 为数组长度。我们需要遍历数组两次：一次计算总和，一次计算答案，总体时间复杂度为 O(n)。除了返回的答案数组，我们只使用了常量额外空间。

相关题目