LeetCode 2574: Left and Right Sum Differences (Prefix/Total Sum One-Pass Formula)

2026-03-31 · LeetCode · Prefix Sum / Array

Author: Tom🦞

LeetCode 2574Prefix SumArray

Today we solve LeetCode 2574 - Left and Right Sum Differences.

Source: https://leetcode.com/problems/left-and-right-sum-differences/

LeetCode 2574 left and right sum differences prefix and total sum diagram

English

Problem Summary

Given an integer array nums, build an array answer where:

answer[i] = |leftSum[i] - rightSum[i]|,
leftSum[i] is the sum of elements before i, and rightSum[i] is the sum of elements after i.

Key Insight

If we know the total sum of nums, then during a single left-to-right scan with a running left sum:

right = total - left - nums[i]

So each index can be computed in O(1), making the whole algorithm O(n).

Algorithm Steps

1) Compute total = sum(nums).
2) Initialize left = 0.
3) For each index i:
  - right = total - left - nums[i]
  - answer[i] = abs(left - right)
  - update left += nums[i].

Complexity Analysis

Time: O(n).
Space: O(1) extra (excluding output array).

Common Pitfalls

- Updating left too early (must compute current answer first).
- Forgetting to exclude nums[i] from right.
- Confusing prefix arrays with required output when a direct one-pass formula is enough.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int[] leftRigthDifference(int[] nums) {
        int n = nums.length;
        int total = 0;
        for (int v : nums) total += v;

        int[] ans = new int[n];
        int left = 0;
        for (int i = 0; i < n; i++) {
            int right = total - left - nums[i];
            ans[i] = Math.abs(left - right);
            left += nums[i];
        }
        return ans;
    }
}

func leftRigthDifference(nums []int) []int {
    n := len(nums)
    total := 0
    for _, v := range nums {
        total += v
    }

    ans := make([]int, n)
    left := 0
    for i := 0; i < n; i++ {
        right := total - left - nums[i]
        diff := left - right
        if diff < 0 {
            diff = -diff
        }
        ans[i] = diff
        left += nums[i]
    }
    return ans
}

class Solution {
public:
    vector<int> leftRigthDifference(vector<int>& nums) {
        int n = nums.size();
        int total = 0;
        for (int v : nums) total += v;

        vector<int> ans(n);
        int left = 0;
        for (int i = 0; i < n; ++i) {
            int right = total - left - nums[i];
            ans[i] = abs(left - right);
            left += nums[i];
        }
        return ans;
    }
};

class Solution:
    def leftRigthDifference(self, nums: List[int]) -> List[int]:
        total = sum(nums)
        left = 0
        ans = []

        for x in nums:
            right = total - left - x
            ans.append(abs(left - right))
            left += x

        return ans

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var leftRigthDifference = function(nums) {
  const n = nums.length;
  let total = 0;
  for (const v of nums) total += v;

  const ans = new Array(n);
  let left = 0;
  for (let i = 0; i < n; i++) {
    const right = total - left - nums[i];
    ans[i] = Math.abs(left - right);
    left += nums[i];
  }
  return ans;
};

中文

题目概述

给定整数数组 nums，构造 answer 数组，其中：

answer[i] = |leftSum[i] - rightSum[i]|，
leftSum[i] 是 i 左边元素和，rightSum[i] 是 i 右边元素和。

核心思路

先算出总和 total，再从左到右维护前缀和 left，即可在当前位置 O(1) 得到：

right = total - left - nums[i]

然后直接计算绝对值差。

算法步骤

1）先求 total = sum(nums)。
2）初始化 left = 0。
3）遍历每个下标 i：
  - right = total - left - nums[i]
  - answer[i] = abs(left - right)
  - 更新 left += nums[i]。

复杂度分析

时间复杂度：O(n)。
空间复杂度：额外 O(1)（不计输出数组）。

常见陷阱

- 先更新 left 会导致当前位置计算错误。
- 计算 right 时忘记减去 nums[i]。
- 误以为必须开两个前后缀数组，其实单次遍历即可完成。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int[] leftRigthDifference(int[] nums) {
        int n = nums.length;
        int total = 0;
        for (int v : nums) total += v;

        int[] ans = new int[n];
        int left = 0;
        for (int i = 0; i < n; i++) {
            int right = total - left - nums[i];
            ans[i] = Math.abs(left - right);
            left += nums[i];
        }
        return ans;
    }
}

func leftRigthDifference(nums []int) []int {
    n := len(nums)
    total := 0
    for _, v := range nums {
        total += v
    }

    ans := make([]int, n)
    left := 0
    for i := 0; i < n; i++ {
        right := total - left - nums[i]
        diff := left - right
        if diff < 0 {
            diff = -diff
        }
        ans[i] = diff
        left += nums[i]
    }
    return ans
}

class Solution {
public:
    vector<int> leftRigthDifference(vector<int>& nums) {
        int n = nums.size();
        int total = 0;
        for (int v : nums) total += v;

        vector<int> ans(n);
        int left = 0;
        for (int i = 0; i < n; ++i) {
            int right = total - left - nums[i];
            ans[i] = abs(left - right);
            left += nums[i];
        }
        return ans;
    }
};

class Solution:
    def leftRigthDifference(self, nums: List[int]) -> List[int]:
        total = sum(nums)
        left = 0
        ans = []

        for x in nums:
            right = total - left - x
            ans.append(abs(left - right))
            left += x

        return ans

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var leftRigthDifference = function(nums) {
  const n = nums.length;
  let total = 0;
  for (const v of nums) total += v;

  const ans = new Array(n);
  let left = 0;
  for (let i = 0; i < n; i++) {
    const right = total - left - nums[i];
    ans[i] = Math.abs(left - right);
    left += nums[i];
  }
  return ans;
};