LeetCode-Book 题解精讲：1480. 一维数组的动态和（Running Sum）—

LeetCode-Book 题解精讲：1480. 一维数组的动态和（Running Sum）——从暴力求和到动态规划

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book

本篇基于开源仓库 LeetCode-Book 中《Krahets 笔面试精选 88 题》题解文档 1480. 一维数组的动态和展开，讲解「前缀和 / 一维动态规划」这一高频面试考点的标准解法。读完本文，你将掌握runningSum问题的状态定义与转移方程，理解为什么暴力求和存在大量重复计算，并能用 Python、Java、C++ 三种语言在 $O(N)$ 时间内一次性通过测试。

题目回顾：什么是「一维数组的动态和」

LeetCode 1480 号题目要求：给定一个一维数组nums，返回一个新的数组ans，其中ans[i]等于nums中前i + 1个元素之和，即：

$$ans[i] = \sum_{k=0}^{i} nums[k]$$

例如输入nums = [1, 2, 3, 4, 5]，输出应为[1, 3, 6, 10, 15]。这个「从头累加到当前位置」的结果数组在算法领域有一个更通用的名字——前缀和（Prefix Sum），它是后续解决区间求和、差分数组等问题的基石。

在仓库的测试用例中也可以看到这一对应关系：Python 与 Java 版测试输入均为[1, 2, 3, 4, 5]，C++ 版测试输入为[1, 2, 3, 4]，分别对应 Python 测试用例、Java 测试用例和 C++ 测试用例。

为什么不能用「求和公式暴力求解」

最直观的暴力做法是：对每个位置i，再嵌套一层循环从0累加到i。这样做的总计算量为 $1 + 2 + \dots + n = \frac{n(n+1)}{2}$ 次加法，时间复杂度退化到 $O(N^2)$。

核心问题在于大量重复计算：计算ans[3]时已经把nums[0] + nums[1] + nums[2]加了一遍，而计算ans[4]时又要重新把这些元素再加一遍，前序求和结果完全被丢弃。数组越长，这种重复越严重。

动态规划视角：把问题约化为递推

题解文档给出的破题思路非常精炼：借助「前一个动态和 $f(i-1)$」来计算「当前动态和 $f(i)$」，此题便被约化为了一个简单的动态规划问题。按照动态规划的四个要素组织如下：

状态定义：设前 $i + 1$ 个数字的和为 $f(i)$，即 $f(i) = ans[i]$；
初始状态：$f(0) = nums[0]$，第一个位置的和就是第一个元素本身；
转移方程：$f(i) = f(i - 1) + nums[i]$，当前位置的和 = 前一个位置的和 + 当前元素；
待求数值：$f(n - 1)$，其中 $n$ 为数组nums的长度，即最终返回整个f数组。

这个递推式的本质是前缀和：f(i)保存的是「以当前位置为结尾的前缀累加结果」。由于每个状态只依赖前一个状态，遍历一遍数组即可填满整个dp数组，时间复杂度从 $O(N^2)$ 降到 $O(N)$。

标准题解：三语言实现对照

仓库 selected_coding_interview/codes 目录下为每道题都提供了带可运行测试驱动的三语言实现，本题对应文件为：

Python 实现
Java 实现
C++ 实现

以下是文档与源码一致的标准解法（均新建dp数组保存结果，不修改输入）：

class Solution: def runningSum(self, nums: List[int]) -> List[int]: dp = [0] * len(nums) dp[0] = nums[0] for i in range(1, len(nums)): dp[i] = dp[i - 1] + nums[i] return dp

class Solution { public int[] runningSum(int[] nums) { int[] dp = new int[nums.length]; dp[0] = nums[0]; for (int i = 1; i < nums.length; i++) { dp[i] = dp[i - 1] + nums[i]; } return dp; } }

class Solution { public: vector<int> runningSum(vector<int>& nums) { vector<int> dp(nums.size()); dp[0] = nums[0]; for (int i = 1; i < nums.size(); i++) { dp[i] = dp[i - 1] + nums[i]; } return dp; } };

三个实现逻辑完全一致，只是语言语法差异：Python 用List[int]类型注解（来自仓库 include 工具包导出的typing.List），Java 用int[]数组，C++ 用std::vector<int>。初始化时先将dp[0]置为nums[0]，再从i = 1开始递推，避免了越界访问。

直接运行仓库源码验证

仓库为每个实现都附带了可直接运行的测试驱动（Driver Code）：

Python：python selected_coding_interview/codes/python/lc_1480_running_sum_of_1d_array.py，输出[1, 3, 6, 10, 15]；
Java：javac -encoding UTF-8 selected_coding_interview/codes/java/lc_1480_running_sum_of_1d_array/lc_1480_running_sum_of_1d_array.java && java lc_1480_running_sum_of_1d_array.lc_1480_running_sum_of_1d_array；
C++：使用g++编译selected_coding_interview/codes/cpp/lc_1480_running_sum_of_1d_array/lc_1480_running_sum_of_1d_array_s1.cpp（需包含同目录 include 头文件），运行后通过PrintUtil::printVector输出结果向量。

关键讨论：是否可以原地修改`nums`

题解文档特别提醒了一个容易被忽视的细节：细心的我们发现，如果原地修改nums，可以避免新建dp带来的内存开销。但通常情况下，不应改变输入变量，因此不建议原地修改nums数组。

原地版本只需要一行核心改动：nums[i] += nums[i - 1]，空间复杂度可降为严格意义上的 $O(1)$ 辅助空间。但工程实践中输入参数往往被其他逻辑复用（例如后续题目 724 题「寻找数组的中心下标」仍需要基于原始数组计算总和），贸然原地覆盖会破坏数据，产生难以排查的副作用。因此在笔试面试中，默认优先使用新建dp数组的写法，这是仓库源码采纳的约定。

复杂度分析

时间复杂度 $O(N)$：只需遍历一次nums，每个元素做一次加法；
空间复杂度 $O(1)$：用于保存结果的dp数组是题目要求必须返回的输出空间，此处不计入辅助空间，因此算法本身没有额外内存开销（若将输出空间计入则为 $O(N)$）。

延伸：从前缀和看一维 DP 的通用模式

本题的转移方程 $f(i) = f(i-1) + nums[i]$ 是一维动态规划中最基础的形态：状态只与前一个状态相关，无需保存整个历史。理解这一模式后，可以自然迁移到同仓库中的其他「扫描累加」类题目：

1. 寻找数组的中心下标：在 lc_724_find_pivot_index.py 中，先求全数组总和，再边扫描边维护左侧累加和sum_left，判断左右是否相等——同样是前缀和思想的应用；
1. 最大子数组和、238. 除自身以外数组的乘积也都建立在前缀累加（累积）的技巧之上。

掌握「用一个变量承接前序结果、单次扫描完成递推」的范式，你就抓住了这一系列题目的共性。建议对照题目分类中相关文档与三语言源码目录逐一验证运行，将知识固化为解题直觉。

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

LeetCode-Book 题解精讲：1480. 一维数组的动态和（Running Sum）——从暴力求和到动态规划