LeetCode-Go 题解精讲1480. Running Sum of 1d Array一维数组动态和 / 前缀和入门【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 1480 题「Running Sum of 1d Array」展开结合本仓库LeetCode-Go中该题的 Go 实现 与 单元测试讲清「一维数组动态和」的定义、前缀和Prefix Sum的递推原理、Go 代码的写法与复杂度分析并把它与 303. Range Sum Query 等进阶题目衔接帮助读者从这道 Easy 题建立起前缀和思想的完整认知。读完本文你将能够独立推导动态和公式、写出两种等价实现并理解前缀和为何能成为区间求和问题的通用武器。题目定义什么是数组的「动态和」题目原文如下Given an arraynums. We define a running sum of an array asrunningSum[i] sum(nums[0]…nums[i]). Return the running sum ofnums.翻译过来就是给你一个数组nums数组「动态和」Running Sum的计算公式为runningSum[i] sum(nums[0]…nums[i])即第i个位置的动态和等于原数组从下标0累加到下标i的所有元素之和最终返回一个与nums等长的新数组。三个官方示例示例 1Input: nums [1,2,3,4] Output: [1,3,6,10] Explanation: Running sum is obtained as follows: [1, 12, 123, 1234].示例 2Input: nums [1,1,1,1,1] Output: [1,2,3,4,5] Explanation: Running sum is obtained as follows: [1, 11, 111, 1111, 11111].示例 3Input: nums [3,1,2,10,1] Output: [3,4,6,16,17]示例 3 可以展开验证[3, 31, 312, 31210, 312101] [3, 4, 6, 16, 17]。约束条件1 nums.length 1000数组长度至少为 1无需处理空数组边界-10^6 nums[i] 10^6元素可为负数但单元素与长度上限决定了中间累加和不会超过1000 × 10^6 10^9在 Go 的int64 位平台为 64 位范围内不存在溢出风险。题目难度为Easy在 仓库 README 的题目总表 中记录通过率为 89.8%是前缀和专题最典型的入门题。解题思路前缀和的递推本质原文档的解题思路只有一句话「简单题按照题意依次循环计算前缀和即可」。这句话背后的核心概念就是前缀和Prefix Sum。定义前缀和数组prepre[i]表示原数组nums[0..i-1]的和即前i个元素的总和。它满足递推关系pre[0] 0 pre[i] pre[i-1] nums[i-1] (1 i n)而题目要求的动态和runningSum[i]恰好等于pre[i1]两者是同一件事的两种表述。因此求解过程就是一趟从左到右的线性扫描初始化累加器为 0每遇到一个元素nums[i]就把当前元素累加上去把累加结果写入结果数组的第i个位置。整个过程只需要遍历数组一次每个元素只访问一次时间复杂度 O(n)空间复杂度 O(n)结果数组本身占用的空间若按题目要求的返回值计算也可视为输出空间若不把返回值计入辅助空间则原地累加思路下额外空间为 O(1)。值得注意的是前缀和的思想是后续一大类题目的地基区间求和、子数组计数、二维矩阵前缀和等都建立在这条递推式之上。本题就是理解这些进阶题的第一步。Go 实现仓库的官方写法逐行拆解仓库中该题的实现位于 leetcode/1480.Running-Sum-of-1d-Array/1480. Running Sum of 1d Array.go完整代码如下package leetcode func runningSum(nums []int) []int { dp : make([]int, len(nums)1) dp[0] 0 for i : 1; i len(nums); i { dp[i] dp[i-1] nums[i-1] } return dp[1:] }这段代码的核心设计是「前缀和数组 首哨兵」模式逐行拆解如下行代码作用1package leetcode该仓库所有题解统一放在leetcode包下便于用一条go test ./leetcode/...跑全部用例见 gotest.sh2func runningSum(nums []int) []int函数签名与 LeetCode 原题保持一致入参、返回值均为[]int3dp : make([]int, len(nums)1)申请长度n1的前缀和数组多出的 1 个位置用作哨兵dp[0]避免在循环里写if i 0分支4dp[0] 0显式初始化前缀和起点为 0数学上对应「前 0 个元素的和为 0」5-7for i : 1; i len(nums); i { dp[i] dp[i-1] nums[i-1] }核心递推dp[i]由上一个前缀和dp[i-1]加上当前元素nums[i-1]得到。这里用nums[i-1]而非nums[i]是因为dp比nums多一个哨兵位索引存在 1 的偏移8return dp[1:]去掉哨兵dp[0]返回长度为n的动态和数组恰好对应runningSum[i] dp[i1]哨兵位技巧的价值在于把「首元素需要特殊处理」的边界情况消解为统一递推循环体内没有分支判断代码更简洁、更不易出错。这与动态规划中常见的「dp[0]虚拟节点」手法一脉相承——事实上本题的递推式与一维 DP 完全同构因此仓库用dp来命名这个数组。另一种等价的直观写法如果不使用哨兵位也可以写成「原地累加 即时输出」的形式逻辑更贴近题目字面描述func runningSum(nums []int) []int { ans : make([]int, len(nums)) sum : 0 for i, v : range nums { sum v ans[i] sum } return ans }两种写法的时间复杂度都是 O(n)空间复杂度都是 O(n)。哨兵写法把「前缀和数组」完整保留下来方便日后扩展到区间查询直观写法代码更短。建议先理解后者贴合题意再掌握前者贴合前缀和/DP 的通用范式。测试验证仓库如何保证正确性本仓库的项目描述强调 100% test coverage每一道题都配有同名_test.go文件。本题的测试位于 leetcode/1480.Running-Sum-of-1d-Array/1480. Running Sum of 1d Array_test.go采用了该仓库统一的「表驱动测试」风格package leetcode import ( fmt testing ) type question1480 struct { para1480 ans1480 } // para 是参数 // one 代表第一个参数 type para1480 struct { nums []int } // ans 是答案 // one 代表第一个答案 type ans1480 struct { one []int } func Test_Problem1480(t *testing.T) { qs : []question1480{ { para1480{[]int{1, 2, 3, 4}}, ans1480{[]int{1, 3, 6, 10}}, }, { para1480{[]int{1, 1, 1, 1, 1}}, ans1480{[]int{1, 2, 3, 4, 5}}, }, { para1480{[]int{3, 1, 2, 10, 1}}, ans1480{[]int{3, 4, 6, 16, 17}}, }, } fmt.Printf(------------------------Leetcode Problem 1480------------------------\n) for _, q : range qs { _, p : q.ans1480, q.para1480 fmt.Printf(【input】:%v 【output】:%v \n, p, runningSum(p.nums)) } fmt.Printf(\n\n\n) }测试结构解读每道题定义一个question1480结构体把输入para1480本题为nums []int与期望输出ans1480本题为one []int打包在一起构成一组测试用例三个用例与原题文档中的三个示例一一对应[1,2,3,4]、[1,1,1,1,1]、[3,1,2,10,1]覆盖了「连续递增」「全相同」「含较大值」三类输入形态循环中对每组用例调用runningSum(p.nums)并打印输入输出方便人工核对。在仓库根目录下运行以下命令即可验证本题及全部题解的正确性与覆盖率参考 gotest.sh 的写法# 运行全部 leetcode 题解测试 go test ./leetcode/... # 带覆盖率统计生成 coverage.txt go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...本项目使用 Go 1.19见 go.mod直接以go run/go test即可在本地复现结果。举一反三从前缀和走向区间求和完成 1480 之后建议按下面这条脉络继续巩固前缀和思想303. Range Sum Query - Immutable同样是前缀和的直接应用。题目要求多次查询sumRange(i, j)若每次都重新累加单次查询是 O(n)而先用 O(n) 构建前缀和数组后sumRange(i, j) pre[j1] - pre[i]单次查询降到 O(1)。这正是 1480 里那个dp数组的完整形态——1480 要求输出所有前缀303 则要求用前缀做任意区间查询二维版本如 304. Range Sum Query 2D - Immutable把一维递推推广到二维容斥公式「子数组求和等于目标值」类计数问题如 560. Subarray Sum Equals K配合哈希表把 O(n²) 优化到 O(n)。可见1480 虽然只是一道 Easy 题但它承载的「哨兵前缀数组 线性递推」模式是整个前缀和算法家族的起点。本文的 Go 实现 runningSum 源码 与 测试用例 均可直接在仓库中查看与运行作为刷题与复习的参照。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解精讲：1480. Running Sum of 1d Array（一维数组动态和 / 前缀和入门）
LeetCode-Go 题解精讲1480. Running Sum of 1d Array一维数组动态和 / 前缀和入门【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 1480 题「Running Sum of 1d Array」展开结合本仓库LeetCode-Go中该题的 Go 实现 与 单元测试讲清「一维数组动态和」的定义、前缀和Prefix Sum的递推原理、Go 代码的写法与复杂度分析并把它与 303. Range Sum Query 等进阶题目衔接帮助读者从这道 Easy 题建立起前缀和思想的完整认知。读完本文你将能够独立推导动态和公式、写出两种等价实现并理解前缀和为何能成为区间求和问题的通用武器。题目定义什么是数组的「动态和」题目原文如下Given an arraynums. We define a running sum of an array asrunningSum[i] sum(nums[0]…nums[i]). Return the running sum ofnums.翻译过来就是给你一个数组nums数组「动态和」Running Sum的计算公式为runningSum[i] sum(nums[0]…nums[i])即第i个位置的动态和等于原数组从下标0累加到下标i的所有元素之和最终返回一个与nums等长的新数组。三个官方示例示例 1Input: nums [1,2,3,4] Output: [1,3,6,10] Explanation: Running sum is obtained as follows: [1, 12, 123, 1234].示例 2Input: nums [1,1,1,1,1] Output: [1,2,3,4,5] Explanation: Running sum is obtained as follows: [1, 11, 111, 1111, 11111].示例 3Input: nums [3,1,2,10,1] Output: [3,4,6,16,17]示例 3 可以展开验证[3, 31, 312, 31210, 312101] [3, 4, 6, 16, 17]。约束条件1 nums.length 1000数组长度至少为 1无需处理空数组边界-10^6 nums[i] 10^6元素可为负数但单元素与长度上限决定了中间累加和不会超过1000 × 10^6 10^9在 Go 的int64 位平台为 64 位范围内不存在溢出风险。题目难度为Easy在 仓库 README 的题目总表 中记录通过率为 89.8%是前缀和专题最典型的入门题。解题思路前缀和的递推本质原文档的解题思路只有一句话「简单题按照题意依次循环计算前缀和即可」。这句话背后的核心概念就是前缀和Prefix Sum。定义前缀和数组prepre[i]表示原数组nums[0..i-1]的和即前i个元素的总和。它满足递推关系pre[0] 0 pre[i] pre[i-1] nums[i-1] (1 i n)而题目要求的动态和runningSum[i]恰好等于pre[i1]两者是同一件事的两种表述。因此求解过程就是一趟从左到右的线性扫描初始化累加器为 0每遇到一个元素nums[i]就把当前元素累加上去把累加结果写入结果数组的第i个位置。整个过程只需要遍历数组一次每个元素只访问一次时间复杂度 O(n)空间复杂度 O(n)结果数组本身占用的空间若按题目要求的返回值计算也可视为输出空间若不把返回值计入辅助空间则原地累加思路下额外空间为 O(1)。值得注意的是前缀和的思想是后续一大类题目的地基区间求和、子数组计数、二维矩阵前缀和等都建立在这条递推式之上。本题就是理解这些进阶题的第一步。Go 实现仓库的官方写法逐行拆解仓库中该题的实现位于 leetcode/1480.Running-Sum-of-1d-Array/1480. Running Sum of 1d Array.go完整代码如下package leetcode func runningSum(nums []int) []int { dp : make([]int, len(nums)1) dp[0] 0 for i : 1; i len(nums); i { dp[i] dp[i-1] nums[i-1] } return dp[1:] }这段代码的核心设计是「前缀和数组 首哨兵」模式逐行拆解如下行代码作用1package leetcode该仓库所有题解统一放在leetcode包下便于用一条go test ./leetcode/...跑全部用例见 gotest.sh2func runningSum(nums []int) []int函数签名与 LeetCode 原题保持一致入参、返回值均为[]int3dp : make([]int, len(nums)1)申请长度n1的前缀和数组多出的 1 个位置用作哨兵dp[0]避免在循环里写if i 0分支4dp[0] 0显式初始化前缀和起点为 0数学上对应「前 0 个元素的和为 0」5-7for i : 1; i len(nums); i { dp[i] dp[i-1] nums[i-1] }核心递推dp[i]由上一个前缀和dp[i-1]加上当前元素nums[i-1]得到。这里用nums[i-1]而非nums[i]是因为dp比nums多一个哨兵位索引存在 1 的偏移8return dp[1:]去掉哨兵dp[0]返回长度为n的动态和数组恰好对应runningSum[i] dp[i1]哨兵位技巧的价值在于把「首元素需要特殊处理」的边界情况消解为统一递推循环体内没有分支判断代码更简洁、更不易出错。这与动态规划中常见的「dp[0]虚拟节点」手法一脉相承——事实上本题的递推式与一维 DP 完全同构因此仓库用dp来命名这个数组。另一种等价的直观写法如果不使用哨兵位也可以写成「原地累加 即时输出」的形式逻辑更贴近题目字面描述func runningSum(nums []int) []int { ans : make([]int, len(nums)) sum : 0 for i, v : range nums { sum v ans[i] sum } return ans }两种写法的时间复杂度都是 O(n)空间复杂度都是 O(n)。哨兵写法把「前缀和数组」完整保留下来方便日后扩展到区间查询直观写法代码更短。建议先理解后者贴合题意再掌握前者贴合前缀和/DP 的通用范式。测试验证仓库如何保证正确性本仓库的项目描述强调 100% test coverage每一道题都配有同名_test.go文件。本题的测试位于 leetcode/1480.Running-Sum-of-1d-Array/1480. Running Sum of 1d Array_test.go采用了该仓库统一的「表驱动测试」风格package leetcode import ( fmt testing ) type question1480 struct { para1480 ans1480 } // para 是参数 // one 代表第一个参数 type para1480 struct { nums []int } // ans 是答案 // one 代表第一个答案 type ans1480 struct { one []int } func Test_Problem1480(t *testing.T) { qs : []question1480{ { para1480{[]int{1, 2, 3, 4}}, ans1480{[]int{1, 3, 6, 10}}, }, { para1480{[]int{1, 1, 1, 1, 1}}, ans1480{[]int{1, 2, 3, 4, 5}}, }, { para1480{[]int{3, 1, 2, 10, 1}}, ans1480{[]int{3, 4, 6, 16, 17}}, }, } fmt.Printf(------------------------Leetcode Problem 1480------------------------\n) for _, q : range qs { _, p : q.ans1480, q.para1480 fmt.Printf(【input】:%v 【output】:%v \n, p, runningSum(p.nums)) } fmt.Printf(\n\n\n) }测试结构解读每道题定义一个question1480结构体把输入para1480本题为nums []int与期望输出ans1480本题为one []int打包在一起构成一组测试用例三个用例与原题文档中的三个示例一一对应[1,2,3,4]、[1,1,1,1,1]、[3,1,2,10,1]覆盖了「连续递增」「全相同」「含较大值」三类输入形态循环中对每组用例调用runningSum(p.nums)并打印输入输出方便人工核对。在仓库根目录下运行以下命令即可验证本题及全部题解的正确性与覆盖率参考 gotest.sh 的写法# 运行全部 leetcode 题解测试 go test ./leetcode/... # 带覆盖率统计生成 coverage.txt go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...本项目使用 Go 1.19见 go.mod直接以go run/go test即可在本地复现结果。举一反三从前缀和走向区间求和完成 1480 之后建议按下面这条脉络继续巩固前缀和思想303. Range Sum Query - Immutable同样是前缀和的直接应用。题目要求多次查询sumRange(i, j)若每次都重新累加单次查询是 O(n)而先用 O(n) 构建前缀和数组后sumRange(i, j) pre[j1] - pre[i]单次查询降到 O(1)。这正是 1480 里那个dp数组的完整形态——1480 要求输出所有前缀303 则要求用前缀做任意区间查询二维版本如 304. Range Sum Query 2D - Immutable把一维递推推广到二维容斥公式「子数组求和等于目标值」类计数问题如 560. Subarray Sum Equals K配合哈希表把 O(n²) 优化到 O(n)。可见1480 虽然只是一道 Easy 题但它承载的「哨兵前缀数组 线性递推」模式是整个前缀和算法家族的起点。本文的 Go 实现 runningSum 源码 与 测试用例 均可直接在仓库中查看与运行作为刷题与复习的参照。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考