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_{k0}^{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(n1)}{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 dpclass 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: vectorint runningSum(vectorint nums) { vectorint 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.ListJava 用int[]数组C 用std::vectorint。初始化时先将dp[0]置为nums[0]再从i 1开始递推避免了越界访问。直接运行仓库源码验证仓库为每个实现都附带了可直接运行的测试驱动Driver CodePythonpython selected_coding_interview/codes/python/lc_1480_running_sum_of_1d_array.py输出[1, 3, 6, 10, 15]Javajavac -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_arrayC使用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]$ 是一维动态规划中最基础的形态状态只与前一个状态相关无需保存整个历史。理解这一模式后可以自然迁移到同仓库中的其他「扫描累加」类题目寻找数组的中心下标在 lc_724_find_pivot_index.py 中先求全数组总和再边扫描边维护左侧累加和sum_left判断左右是否相等——同样是前缀和思想的应用最大子数组和、238. 除自身以外数组的乘积 也都建立在前缀累加累积的技巧之上。掌握「用一个变量承接前序结果、单次扫描完成递推」的范式你就抓住了这一系列题目的共性。建议对照 题目分类 中相关文档与 三语言源码目录 逐一验证运行将知识固化为解题直觉。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 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_{k0}^{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(n1)}{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 dpclass 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: vectorint runningSum(vectorint nums) { vectorint 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.ListJava 用int[]数组C 用std::vectorint。初始化时先将dp[0]置为nums[0]再从i 1开始递推避免了越界访问。直接运行仓库源码验证仓库为每个实现都附带了可直接运行的测试驱动Driver CodePythonpython selected_coding_interview/codes/python/lc_1480_running_sum_of_1d_array.py输出[1, 3, 6, 10, 15]Javajavac -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_arrayC使用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]$ 是一维动态规划中最基础的形态状态只与前一个状态相关无需保存整个历史。理解这一模式后可以自然迁移到同仓库中的其他「扫描累加」类题目寻找数组的中心下标在 lc_724_find_pivot_index.py 中先求全数组总和再边扫描边维护左侧累加和sum_left判断左右是否相等——同样是前缀和思想的应用最大子数组和、238. 除自身以外数组的乘积 也都建立在前缀累加累积的技巧之上。掌握「用一个变量承接前序结果、单次扫描完成递推」的范式你就抓住了这一系列题目的共性。建议对照 题目分类 中相关文档与 三语言源码目录 逐一验证运行将知识固化为解题直觉。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考