LeetCode 每日一题笔记

0. 前言

• 日期：2026.06.04
• 题目：2574. 左右元素和的差值
• 难度：简单
• 标签：数组、前缀和

1. 题目理解

问题描述 给定数组nums，leftSum[i]为下标i左侧所有元素之和，rightSum[i]为下标i右侧所有元素之和，构造答案数组ans[i]=|leftSum[i]-rightSum[i]。

示例

输入：nums = [10,4,8,3] 输出：[15,1,11,22] 解释：leftSum=[0,10,14,22]，rightSum=[15,11,3,0]，逐项求绝对值差得到结果。

2. 解题思路

核心观察

1. 原思路：分别预处理左侧前缀和、右侧后缀和两个数组，再逐项求差值；
2. 优化思路：先统计数组总和，遍历过程动态维护左和、右和，右和初始为总和，遍历时先减掉当前元素即为右侧和，计算完答案再累加至左和，仅用常数额外变量。

算法步骤

1. 优化版：先累加全部元素得到初始右总和；
2. 逐个遍历数组：
   • 右总和减去当前值，得到当前位置右侧和；
   • 计算左右和绝对值存入答案；
   • 当前值累加到左侧和；
3. 遍历结束返回答案数组。

3. 代码实现

package lc2574;
class Solution {
    public int[] leftRightDifference(int[] nums) {
        int n = nums.length;
        int [] prefixL  = new int[n];
        prefixL[0]=nums[0];
        for (int i = 1; i < n; i++) {
            prefixL[i]=nums[i]+prefixL[i-1];
        }

        int [] prefixR  = new int[n];
        prefixR[n-1]=nums[n-1];
        for (int i = n-1; i >=0; i--) {
            prefixR[i]=nums[i]+prefixR[i+1];
        }

        for (int i = 0; i < n; i++) {
            nums[i]=Math.abs(prefixR[i]-prefixL[i]);
        }
        return nums;
    }
}

4. 代码优化说明

class Solution {
public int[] leftRightDifference(int[] nums) {
    int n = nums.length, right_sum = 0;
    // 先统计数组全部元素总和，作为右侧和初始值
    for (int num: nums) right_sum += num;
    int[] ans = new int[n];
    int left_sum = 0;
    for (int i = 0; i < n; i++) {
        right_sum -= nums[i]; // 剔除当前元素，剩余就是i右侧所有元素和
        ans[i] = Math.abs(right_sum - left_sum); // 计算左右和的绝对值差
        left_sum += nums[i]; // 当前元素归入左侧和，供下一轮使用
    }
    return ans;
}
}

5. 复杂度分析

• 双数组前缀和原版 时间：$O(n)$，三次线性遍历； 空间：$O(n)$，两个前缀和数组。
• 空间优化版 时间：$O(n)$，两次线性遍历； 空间：$O(n)$（仅答案数组必要开销），额外临时变量$O(1)$。

6. 总结

• 原版思路直观，通过前后缀数组分别存储左右累加和；
• 优化利用总和动态更新左右和，省去两个前缀数组，空间开销大幅降低；
• 关键：right_sum -= nums[i]得到当前右侧和，left_sum += nums[i]更新左侧和。