2574. 左右元素和的差值 Left and Right Sum Differences

问题描述

这是一个简单的前缀和 prefix sum 问题.

Prefix sum

处理思路如下:

1. 计算 left_sum, 从左到右遍历原数组, 并计算前缀和, left_sum[i + 1] = left_sum[i] + nums[i]
2. 计算 right_sum 从左到右遍历原数组, 并计算前缀和, right_sum[i - 1] = right_sum[i] + nums[i]
3. 计算遍历两个数组, 并计算 (left_sum[i] - right_sum[i]).abs(), 就得到了答案

#![allow(unused)]
fn main() {
// Prefix Sum
pub fn left_right_difference1(nums: Vec<i32>) -> Vec<i32> {
    debug_assert!(!nums.is_empty());

    let len = nums.len();
    let mut left_sum = vec![0; len];
    left_sum[0] = 0;
    // 从左向右遍历
    for i in 0..(len - 1) {
        left_sum[i + 1] = left_sum[i] + nums[i];
    }
    //println!("left sum: {left_sum:?}");

    let mut right_sum = vec![0; len];
    right_sum[0] = 0;
    // 从右向左遍历
    for i in (1..=(len - 1)).rev() {
        right_sum[i - 1] = right_sum[i] + nums[i];
    }
    //println!("right sum: {right_sum:?}");

    left_sum
        .into_iter()
        .zip(right_sum)
        .map(|(left, right)| (left - right).abs())
        .collect()
}
}

该算法的时间复杂度是 O(n), 空间复杂度是 O(n).