豆包MarsCode：前缀和计算问题

问题描述

思路分析

问题理解

小S的任务是计算一个整数数组 nums 的前缀和。前缀和是指从数组开始到某个位置的所有元素的累加值，形成一个新数组。例如：

• 输入数组：nums = [4, 5, 1, 6]
• 前缀和数组：[4, 9, 10, 16]
  • 4 = 4
  • 9 = 4 + 5
  • 10 = 4 + 5 + 1
  • 16 = 4 + 5 + 1 + 6

解决步骤

我们需要构建一个新数组 prefixSum，其元素是输入数组 nums 的前缀和。关键步骤如下：

1. 定义结果数组

• 新建一个数组 prefixSum，长度与输入数组 nums 相同，用于存储前缀和。

2. 特殊情况处理

• 如果数组是空数组（nums.length == 0），直接返回空数组。

3. 逐步计算前缀和

• 第一个位置的前缀和等于数组第一个元素本身：
  • prefixSum[0] = nums[0]
• 从第二个元素开始，每个位置的前缀和等于前一个位置的前缀和加上当前元素：
  • prefixSum[i] = prefixSum[i - 1] + nums[i]

4. 遍历数组

• 使用循环遍历数组，从第一个元素累加到最后一个元素，将每次计算的结果存入 prefixSum。

伪代码总结

1. 创建结果数组 prefixSum，长度与 nums 相同。
2. 如果 nums 为空，则直接返回 prefixSum。
3. 将 prefixSum[0] 初始化为 nums[0]。
4. 遍历数组，从第二个元素开始：
   • prefixSum[i] = prefixSum[i - 1] + nums[i]
5. 返回结果数组 prefixSum。

核心公式

• 对于数组的第 $i$ 个位置，前缀和的计算公式为：

  $prefixSum[i]=prefixSum[i-1]+nums[i]$

• 边界条件：第一个元素：

  $prefixSum[0]=nums[0]$

参考代码（Java）

public class Main {
    public static int[] solution(int[] nums) {
  
        int[] prefixSum = new int[nums.length];
        if (nums.length == 0) return prefixSum;

        // 初始化第一个元素
        prefixSum[0] = nums[0];

        // 计算其余元素的前缀和
        for (int i = 1; i < nums.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i];
        }

        return prefixSum;
    }

    public static void main(String[] args) {
        System.out.println(java.util.Arrays.equals(solution(new int[]{4, 5, 1, 6}), new int[]{4, 9, 10, 16}));
        System.out.println(java.util.Arrays.equals(solution(new int[]{2, 2, 2, 2}), new int[]{2, 4, 6, 8}));
        System.out.println(java.util.Arrays.equals(solution(new int[]{7, 3, 9, 4}), new int[]{7, 10, 19, 23}));
        System.out.println(java.util.Arrays.equals(solution(new int[]{1, 2, 3}), new int[]{1, 3, 6}));
    }
}

代码分析

1. 方法签名

public static int[] solution(int[] nums)

• 输入：
  • 参数 nums 是一个整数数组，表示输入数组。
• 输出：
  • 返回一个新的整数数组，表示 nums 的前缀和。

2. 初始化结果数组

int[] prefixSum = new int[nums.length];

• 创建一个与 nums 等长的数组 prefixSum，用于存储计算出来的前缀和。

3. 边界条件检查

if (nums.length == 0) return prefixSum;

• 如果输入数组是空的，则直接返回空的前缀和数组。

4. 初始化第一个前缀和

prefixSum[0] = nums[0];

• 第一个位置的前缀和是输入数组的第一个元素。

5. 循环计算前缀和

for (int i = 1; i < nums.length; i++) {
    prefixSum[i] = prefixSum[i - 1] + nums[i];
}

• 从数组的第二个元素开始：
  • 使用公式：prefixSum[i] = prefixSum[i - 1] + nums[i]
  • 当前的前缀和等于前一个前缀和加上当前元素值。

6. 返回结果

return prefixSum;

• 返回计算好的前缀和数组。

运行过程解析

示例 1: 输入 [4, 5, 1, 6]

• 初始化：prefixSum = [0, 0, 0, 0]
• 步骤：
  • prefixSum[0] = 4
  • prefixSum[1] = prefixSum[0] + nums[1] = 4 + 5 = 9
  • prefixSum[2] = prefixSum[1] + nums[2] = 9 + 1 = 10
  • prefixSum[3] = prefixSum[2] + nums[3] = 10 + 6 = 16
• 结果：[4, 9, 10, 16]

示例 2: 输入 [2, 2, 2, 2]

• 初始化：prefixSum = [0, 0, 0, 0]
• 步骤：
  • prefixSum[0] = 2
  • prefixSum[1] = prefixSum[0] + nums[1] = 2 + 2 = 4
  • prefixSum[2] = prefixSum[1] + nums[2] = 4 + 2 = 6
  • prefixSum[3] = prefixSum[2] + nums[3] = 6 + 2 = 8
• 结果：[2, 4, 6, 8]