1. 为什么一道Easy题值得翻来覆去地做LeetCode 1588这道题名字叫“所有奇数长度子数组的和”难度标着Easy但我一直觉得它是一道被低估的题目。很多刷题的人扫一眼就跳过觉得暴力三重循环能过就完事了但真正把这题吃透的人大概率能从中提炼出一套处理“子数组求和”类问题的通用方法论。先说这题到底在问什么给定一个整数数组arr需要返回所有可能的奇数长度子数组的和。所谓“奇数长度”就是子数组的长度为1、3、5、7……这样递增下去。注意子数组必须是连续的跟子序列完全是两码事。比如arr [1, 4, 2, 5, 3]长度1的子数组有五个长度3的有三个长度5的有一个把所有这些子数组的元素各自求和再全部加起来就是答案。这题适合谁来看我觉得三类人都应该认真做一遍一是刚入门刷题想搞清楚暴力枚举、前缀和、数学推导这三种思路怎么递进的新手二是准备面试想在“数组求和”这个高频考点上建立体系化认识的求职者三是那些刷题已经有一阵子但做题靠背模板、不深究原理的朋友——这一题真的能把“为什么”讲明白。我在刷这题时的最大感受是它表面考的是子数组遍历但真正想让你理解的是“每个元素会被多少个子数组覆盖”这个视角。一旦切换到这种视角很多类似题目比如所有子数组的最小值之和、区间查询类问题都会豁然开朗。接下来我从最粗暴的解法开始一层层往上拆。2. 先把暴力解法写到极致——理解枚举的核心逻辑2.1 如何准确枚举所有奇数长度子数组暴力解法的思路非常直观枚举所有长度是奇数的子数组逐一求和。但“枚举所有子数组”这个操作新手最常犯的错误是枚举“起点和终点”时搞错边界。我建议把子数组的枚举理解成两件事先定起点再定长度。具体来说外层循环用i表示起点范围从0到n-1内层循环用length表示子数组长度从1开始每次加2直到i length不超过数组长度。这样做有两个好处一是长度始终是奇数不会多算二是起点i和长度length确定了终点就是i length - 1天然满足闭区间的要求不容易出现越界。举个实际例子arr [1, 4, 2, 5, 3]i 0时length可以取1、3、5对应的子数组分别是[1]、[1, 4, 2]、[1, 4, 2, 5, 3]i 1时length取1、3对应[4]、[4, 2, 5]。这样枚举下来不会漏也不会重复。确定好子数组的范围后第三步就是通过第三层循环从起点累加到终点把子数组的和算出来。这个过程最直白但也最容易忽略一个细节子数组的和是可以复用的。如果你在第三层循环里每次都从零开始加那复杂度就是O(n^3)虽然这题n的范围是100O(n^3)也只有一百万次运算完全能通过但如果是n等于一万呢所以暴力解法只是用来建立直觉的起点不是终点。2.2 暴力解法实测溢出风险与剪枝空间我实际写完暴力代码去提交发现一个很有意思的坑答案累加用的是int类型按理说题目给了数组长度最多100、元素范围是1到1000总和上限就是100 * 1000 * (n/2)级别的数值int完全放得下。但如果你把代码写得“通用”一点比如从某个模板里复制来的累加器用的变量名是result且初始化为0在Java或C里没问题在Python里也没问题但如果换成长度更大的数组去测试int就有溢出的可能性。这其实是刷题人的一个习惯问题拿到一道题先看数据范围再选数据类型。arr.length 100arr[i] 1000所有子数组最多有n(n1)/2 5050个其中奇数长度的大约一半每个子数组和最多100 * 1000 100000所以总答案最大也就是2500 * 100000 2.5亿int确实够。但我在实际工程中写区间求和相关的代码时早就习惯用long了因为真实业务数据不会像LeetCode这么温柔。还有一个可以优化的点第三层循环求和时如果length很大很多元素被重复加了多次。暴力解法本质上没有利用任何历史计算这是它慢的根本原因。我见过有朋友在暴力解法的第三层循环里加了一个“如果当前累积和超过某个阈值就提前break”的逻辑试图剪枝——这种优化在这题里是没有意义的因为题目要求累加所有子数组和不存在提前终止的条件。剪枝这招在回溯类题目里好用在纯遍历求和题里基本无用。2.3 暴力代码的一个正确写法参考from typing import List class Solution: def sumOddLengthSubarrays(self, arr: List[int]) - int: n len(arr) total 0 for i in range(n): for length in range(1, n - i 1, 2): # 当前子数组是 arr[i:ilength] for j in range(i, i length): total arr[j] return total这段代码我在本地跑了一下输入是[1, 4, 2, 5, 3]输出58和题目示例一致。暴力解法的代码量最少逻辑最不容易出错适合作为面试时的“保底方案”——就算你没想出优化解法先把暴力写完也能向面试官展示你具备最基本的枚举能力后面再逐步优化这是面试中很实用的递进策略。3. 前缀和优化把O(n^3)降到O(n^2)的关键一步3.1 前缀和数组是怎么消除重复累加的暴力解法慢核心原因在于同一个元素被放进不同子数组里反复求和但每次都从零开始加。比如arr[2]在子数组[0..2]里被算了一次在子数组[1..3]里又被算了一次这两次累加过程完全独立没有任何复用。前缀和的思路就是提前预处理一个数组prefix其中prefix[i]表示arr[0]到arr[i-1]的和。这样一来任意区间[left, right]的和就可以通过prefix[right 1] - prefix[left]在O(1)时间内得到根本不用再去循环累加。这个思想特别像日常生活中记账与其每次花钱都从头把消费记录翻一遍不如随时记下累计金额想知道某段时间花了多少直接拿两个时间点的累计金额相减就行。用前缀和优化后代码的结构从三层循环变成两层循环外层确定起点和长度或起点和终点内层直接通过前缀和数组计算子数组和并累加。复杂度从O(n^3)降到O(n^2)。对于n100来说时间几乎无感但n10000时O(n^2)就是一亿次操作勉强能接受O(n^3)则是一万亿次彻底跑不动。所以前缀和的价值不在这一题的小数据上而在它的通用性上。前缀和的构造有一个细节很容易写错prefix数组的长度通常是n1prefix[0] 0然后prefix[i 1] prefix[i] arr[i]。为什么要多开一位因为这样可以让prefix[right 1] - prefix[left]在left0时也成立避免特判。这个设计我在很多新手的代码里看到过错误版本——有人喜欢开成和arr一样长的数组然后每次算区间和都要判断left是否为0一旦忘记判断结果就错了。多开一位是成本最低的规避方案。3.2 用前缀和重写代码更短思路更清晰from typing import List class Solution: def sumOddLengthSubarrays(self, arr: List[int]) - int: n len(arr) prefix [0] * (n 1) for i in range(n): prefix[i 1] prefix[i] arr[i] total 0 for i in range(n): for length in range(1, n - i 1, 2): total prefix[i length] - prefix[i] return total这段代码提交后运行时间从暴力解法的几毫秒变成了几乎可以忽略的零点几毫秒。更重要的是它把“计算子数组和”这个高频操作从O(length)降到了O(1)这是质变。我建议每一个刷题到中期的朋友都把“区间和用前缀和”变成肌肉记忆而不是每次看到区间就去临时累加。这里还要注意一个边界内层循环的length步长是2从1开始因此i length最大就是n正好对应prefix数组的最后一个有效索引n不会越界。如果你把length当作“到终点的距离”来写写成range(1, n - i 1, 2)这里的n - i 1就是最大长度加一因为range是左闭右开的保证取到最大奇数长度时i length刚好等于n或n-1之类总之不会超过n。我在写的时候曾经把range上限写成n - i结果长度总是少一个最后调试半天才发现是range步长和上限没配合好。3.3 从这个版本开始思考“还能不能更快”O(n^2)的解法已经能轻松应对这题的约束但如果把题目扩展一下改成任意长度连续子数组求和或者改成二维矩阵的子矩阵求和前缀和依然适用只是维度增加了。真正值得思考的是有没有可能做到O(n)我在刷完这题后专门去翻了讨论区看到很多人用“数学贡献法”把复杂度压到O(n)。当时我第一反应是这题真的有必要O(n)吗数据范围决定了暴力就够用但仔细一想如果原题改成arr长度最多10^5元素范围不变O(n^2)就变成了一百亿次操作肯定超时。所以从面试的角度看面试官完全可能把这题的数组长度改大考察你有没有能力从O(n^2)优化到O(n)。这也是我认为这题被严重低估的原因——它是一道能横向展开的题目而很多人只把它当成Easy题随便划走。4. 数学贡献法从“枚举子数组”到“统计元素出现次数”4.1 换个视角每个元素到底要被加多少次前缀和已经够快了但还能不能更快能。做法是彻底抛弃“枚举子数组”的思路改成统计“每个元素arr[i]在所有奇数长度子数组中出现了多少次”然后把arr[i]乘以出现次数最后全部加起来。这个思路可以用一句话概括与其一个个子数组去求和不如问问每个元素被多少个子数组合法地包含。判断一个子数组能否包含arr[i]关键看两点子数组的左边界在哪、右边界在哪。左边界可以取0到i之间的任意位置包括i本身所以左边界的可能数有i 1种右边界可以取i到n-1之间的任意位置所以右边界可能数有n - i种。如果子数组长度没有奇偶限制包含arr[i]的子数组总数就是(i 1) * (n - i)。这很好理解就像排队时一个人能参与的“连续队伍片段”左边可以站0到i个人右边可以站0到n-1-i个人组合起来的数量就是左选择乘以右选择。但题目要求子数组长度必须是奇数所以不能直接拿所有组合数去乘还得分奇偶讨论。这里需要一个关键结论在某个区间内奇数长度的子数组数量只跟这个区间的左右边界奇偶性有关。具体推导方式很多我采用一种容易理解的分类讨论分别统计“包含arr[i]的子数组中左边选了偶数个和奇数个元素的情况数”再统计“右边选了偶数个和奇数个元素的情况数”把左边的奇数情况乘以右边的奇数情况就是左奇右奇组成的子数组长度为奇数奇数1奇数奇数同理把左边的偶数情况乘以右边的偶数情况也得到奇数长度子数组偶数1偶数奇数。4.2 关键公式推导与代码实现先说左右两边奇偶数怎么算。左边共有i 1种选择包括选0个元素到选i个元素。在这i 1种选择里选偶数个元素的情况数可以用公式(left_count 1) // 2来表达吗不行这个公式只在某些情况下成立。正确的是把0到i这i1个数分成奇偶两部分如果i是偶数偶数有i/2 1个奇数有i/2个如果i是奇数偶数有(i1)/2个奇数也是(i1)/2个。一个简洁的写法是左边偶数情况数left_even (i 2) // 2左边奇数情况数left_odd (i 1) // 2。这里用的是整数除法需要仔细验证边界。右边的情况同理一共有n - i种选择对应选了0到n-1-i个右侧元素。右边偶数情况数right_even (n - i 1) // 2右边奇数情况数right_odd (n - i) // 2。把能组成奇数长度子数组的两类组合加起来arr[i]的出现次数 left_even * right_even left_odd * right_odd。你可以手动验算比如arr[0]在i0时left_even 1left_odd 0right_even和right_odd由n决定。以n5为例right_even 3right_odd 2所以arr[0]出现次数 13 02 3。手动枚举验证长度1的子数组包含arr[0]的有[1]长度3的子数组包含arr[0]的有[1,4,2]长度5的有[1,4,2,5,3]共3次正确。代码实现非常简洁from typing import List class Solution: def sumOddLengthSubarrays(self, arr: List[int]) - int: n len(arr) total 0 for i, value in enumerate(arr): left_even (i 2) // 2 left_odd (i 1) // 2 right_even (n - i 1) // 2 right_odd (n - i) // 2 total value * (left_even * right_even left_odd * right_odd) return total这个版本的时间复杂度是O(n)空间复杂度是O(1)。我实测提交运行时间比前缀和版本又快了接近一倍。更重要的是这个公式把整道题的“中心”从“子数组”转移到了“元素”这种视角切换在LeetCode很多中等题里都非常关键。比如“子数组的最小值之和”这类题核心思想就是统计每个最小值能覆盖多少个子数组本质上和这里的“统计每个元素的贡献”是同一个套路。4.3 一个快速验证公式的方法我特别推荐一种验证方法拿n5的数组把每个位置的贡献次数先算出来再用暴力法挨个验证。比如n5时arr[0]出现3次arr[1]出现6次arr[2]出现7次arr[3]出现6次arr[4]出现3次。加起来一共25次这正好等于所有奇数长度子数组的总个数长度为1的有5个长度为3的有3个长度为5的有1个总共有9个子数组不对子数组总个数是5319个但每个子数组的长度不同元素总出现次数是51 33 1*5 59519也不是25。看到这里你可能察觉了我的验证方式出错了。实际上n5时奇数长度子数组总共有9个元素出现总次数应该是长度1的5个子数组贡献5次长度3的3个子数组贡献9次长度5的1个子数组贡献5次总共19次。那按公式算出的25次显然是错的。错在哪里回到我的验证过程left_even (i2)//2left_odd (i1)//2这两个公式在i0时给出left_even1left_odd0正确i2时left_even2left_odd1即左边选0、2个是偶数选1个是奇数正确。但关键在于并不是所有左右奇偶组合都合法——左奇右奇组合成的子数组长度是奇数1奇数奇数左偶右偶组合成的子数组长度是偶数1偶数奇数这两种组合都合法但左奇右偶和左偶右奇就不合法。按这个逻辑n5时每个元素出现次数应该重新算。为了不误导大家我直接用实际枚举来验证公式n5arr [1,4,2,5,3]。所有奇数长度子数组如下——长度1[1]、[4]、[2]、[5]、[3]长度3[1,4,2]、[4,2,5]、[2,5,3]长度5[1,4,2,5,3]。统计次数arr[0]1出现于[1]、[1,4,2]、[1,4,2,5,3]共3次arr[1]4出现于[4]、[1,4,2]、[4,2,5]、[1,4,2,5,3]共4次arr[2]2出现于[2]、[1,4,2]、[4,2,5]、[2,5,3]、[1,4,2,5,3]共5次arr[3]5出现于[5]、[4,2,5]、[2,5,3]、[1,4,2,5,3]共4次arr[4]3出现于[3]、[2,5,3]、[1,4,2,5,3]共3次。总次数3454319和上面手算一致。再用公式算i0left_even1left_odd0right_even3right_odd2出现次数13023对。i1left_even1left_odd1right_even3right_odd2出现次数13125但实际是4。问题出在右边奇偶数公式上n-i4右边可以选择0到3个元素也就是0、1、2、3这4种情况其中偶数情况是0、2共2种奇数情况是1、3共2种。所以right_even2right_odd2。我之前写的right_even(n-i1)//2(41)//22right_odd(n-i)//22居然是对的但代入后出现次数12124就对上了。而我在前面误写成了right_even3是拿n5时i0的情况代入了混淆了。所以正确公式确认如下left_even (i 2) // 2 left_odd (i 1) // 2 right_even (n - i 1) // 2 right_odd (n - i) // 2我再验算i3left_even(32)//22left_odd(31)//22right_even(21)//21right_odd2//21出现次数21214正确。i4left_even3left_odd2right_even(11)//21right_odd1//20出现次数31203正确。这个验证过程想说明什么呢就是写这种带奇偶分类的公式一定不要凭感觉推完就提交最好先用小规模数组对照暴力结果验证一遍。我见过的很多题解直接甩公式看起来高深莫测但其中的整数除法边界和下标差异只有自己验算过才能真正确认不然面试时一紧张公式写错后续推导就全崩了。4.4 为什么数学贡献法值得掌握有人可能会问既然这题n最大100前缀和已经是O(n^2)了何必再学O(n)的数学做法我的回答是如果你只满足于把LeetCode 1588过掉那确实不需要但如果你刷题是为了建立解决问题的能力数学贡献法锻炼的“从元素视角看问题”的思维会直接迁移到一系列经典题目上。举几个例子LeetCode 907“子数组的最小值之和”需要用单调栈找到每个元素作为最小值的辐射范围然后计算它被多少个子数组包含LeetCode 828“统计子串中的唯一字符”本质上是统计每个字符在多少个子串中做出了贡献还有一堆排列组合类的概率题也都是“逐个计算元素贡献再求和”的套路。可以说掌握了“贡献法”你就掌握了一种高级的计数思维这比记住任何一道题的模板都有用。5. 三种解法横向对比与工程实现建议5.1 复杂度与代码量对照表解法时间复杂度空间复杂度核心思想适合场景暴力三重循环O(n^3)O(1)枚举起点、长度后重新累加面试保底n 200前缀和优化O(n^2)O(n)预处理区间和消除重复累加笔试默认方案n 10000数学贡献法O(n)O(1)统计每个元素被奇数长度子数组包含的次数面试进阶展示n可达10^5以上代码量上暴力解法和前缀和版本都很短数学贡献法也不长三者在LeetCode 1588上的运行时间差距在数据量小时几乎看不出差别。但如果你在面试中先给出暴力解然后在面试官引导下逐步给出前缀和、再给出数学贡献法展示的是一条完整的优化链条这在面试官眼里是很好的信号。我在面试别人时最怕看到一种情况候选人上来就直接背一个最优解法问为什么这样做答不上来。反过来如果一个候选人能先把暴力解法写出来然后说清楚暴力慢在哪里再用前缀和去掉一层循环最后提炼出贡献法我会认为他对基础数据结构和数学推导都有扎实的掌握这在工程协作中非常重要。5.2 工程实现层面还要注意什么除了算法本身从工程角度看这题还有几个可以聊聊的点第一代码要写好变量命名。left_even、right_odd这种名字虽然长但一眼能看懂含义比le、ro这种缩写可读性好得多。算法题的代码虽然通常不会进生产环境但面试的时候面试官会看你的命名习惯临时变量一大堆的代码在真实code review里是会挨批的。第二要考虑数据类型的扩展性。虽然这题用int没问题但如果你是复用到真实业务中数组长度和元素范围一旦改大int非常容易溢出。LeetCode题解里经常有“本题答案在int范围内”的注释但我在公司里写统计类功能时几乎全部用long因为线上数据量和测试数据根本不是一个量级。第三测试用例要覆盖边界。这题的边界场景包括数组长度是1时答案就是arr[0]数组所有元素都相等此时可以验证公式是否在n为奇数或偶数时都成立数组元素全为零答案为零。我习惯写完算法后先跑这几个边界再提交能省下很多罚时。5.3 从这题延伸出去的变种题LeetCode 1588本身是一个基础款但它能延伸出不少变种。最简单的是把“奇数长度”改成“偶数长度”那贡献法公式就要改成left_even * right_odd left_odd * right_even再改一下可以让子数组长度为“3的倍数”这就要分组余数了。更进阶的变种是“长度为k的所有子数组的最大值”这类滑动窗口问题虽然解法不同但它们都在锻炼对连续区间内元素贡献的敏感度。我刷题有个习惯做完一道题会自己尝试改一两个条件然后看看能不能快速推导出新解法。比如这题改成长度必须为奇数且元素可正可负那么数学贡献法依然有效因为它不依赖于元素的正负性。这个练习对思维灵活性的提升很有帮助。6. 踩坑记录那些我替大家试过的错误写法6.1 误把“子数组”当“子序列”这是我见过最多新手犯的错误。“子数组”必须是连续的而“子序列”可以不连续。有人看到题目说“所有奇数长度子数组的和”会用回溯或组合的方式去枚举所有奇数长度的子序列然后求和。这样做在小数据量时结果可能碰巧对但数据一复杂就错得离谱。比如[1, 2, 3]的奇数长度子序列包括[1]、[2]、[3]、[1,2,3]而奇数长度子数组也是这三个加一个[1,2,3]碰巧一样但换成[1, 2, 3, 4]子序列还包括[1,3]、[2,4]、[1,4]等等子数组却没有这些结果立刻不同。区分子数组和子序列的关键就是看是否要求在原数组中连续排列。一看到“子数组”三个字下意识就要想到区间[left, right]这个表示方式而不是subset。6.2 求奇偶个数时分不清“元素个数”和“下标个数”这是数学贡献法中最容易踩的坑。我要统计的是“左边选了0个到i个元素”一共i1个数要分奇偶就要看0到i之间有多少个偶数和多少个奇数。很多人把“下标i的奇偶”和“可选择元素个数的奇偶”混在一起导致公式写错。切记下标是下标计数是计数。比如i2时下标2是偶数但左边可选0、1、2个元素偶数选择数是20和2奇数选择数是11所以left_even2left_odd1。如果你把i2的奇偶直接当成选择数的奇偶就会错误地认为left_even1、left_odd2整个公式就废了。写完公式后强烈建议把i0、i1、in-1这几个关键点代入验算一遍。我前文已经演示过验算过程这比任何静态检查都有效。6.3 循环边界中的1/-1错误前缀和版本最容易错的地方在于prefix数组长度是n1所以计算区间和要用prefix[right 1] - prefix[left]。有人图省事把prefix定义成和arr一样长然后写if left 0的特判这种代码在left0时没问题但一旦忘记特判left0时的结果就少了prefix[left]这一段。还有一种错误是长度循环写成range(1, n - i 1, 2)注意这里的n - i 1是最大长度加一而range的上限本身是开区间所以写成range(1, n - i 1, 2)才能取到最大奇数长度。如果你写成range(1, n - i, 2)且n-i恰好是奇数那么最大长度刚好没取到结果少一个子数组。这类边界错误很难用肉眼发现最好写个随机小数组用暴力结果做对拍验证。6.4 对拍验证最推荐的测试方法说到对拍这是我在刷题时最喜欢用的方法。具体做法是写一个绝对正确但可能很慢的暴力解法作为基准再写一个优化解法作为被测对象然后生成多组随机小规模数据比较两者的输出是否一致。LeetCode 1588这种题非常适合对拍因为暴力解法逻辑简单、不容易写错用它来验证前缀和或数学贡献法的正确性非常可靠。Python示例import random def brute_force(arr): n len(arr) total 0 for i in range(n): for length in range(1, n - i 1, 2): total sum(arr[i:ilength]) return total def formula(arr): n len(arr) total 0 for i, value in enumerate(arr): left_even (i 2) // 2 left_odd (i 1) // 2 right_even (n - i 1) // 2 right_odd (n - i) // 2 total value * (left_even * right_even left_odd * right_odd) return total for _ in range(1000): arr [random.randint(1, 10) for _ in range(random.randint(1, 20))] if brute_force(arr) ! formula(arr): print(error:, arr) break else: print(all ok)我建议新手每写一版优化解法都做一次这种对拍不仅在LeetCode 1588很多题目都可以用这个策略。它能在几秒内帮你找出边界错误比自己盯着代码猜半天高效得多。7. 我实际刷这题的一些体会刷题刷到一定阶段你会发现真正拉开差距的往往不是“会不会做某一道题”而是“能不能看出这道题和之前哪道题共享同一个底层思路”。LeetCode 1588就是一个特别典型的例子从暴力到前缀和是一种通用优化手段从前缀和到数学贡献法是一次视角切换。而这个“视角切换”才是算法思维的核心。我自己在做这题时一开始也是直接写前缀和版本跑通后觉得不过瘾才去研究讨论区里的O(n)解法。刚开始看那些left_even、right_odd的公式推导时说实话也被绕晕过——为什么这么简单的题目会有这么“豪华”的公式后来我把它当成一个计数问题重新推导了一遍才彻底搞明白。这种从“看不懂”到“自己推一遍就通了”的过程其实比做十道新题还有价值。如果你正在刷题准备面试或者刚刚开始接触算法我的建议是不要因为这题是Easy就草草跳过试着用三种解法都写一遍再写一个对拍脚本验证最后尝试改一改题目条件看看会发生什么。这套流程走完你对“子数组求和”这个主题的理解会比单纯刷十道同类题更扎实。最后分享一个小技巧LeetCode的讨论区里有很多人写题解时会给出O(n)的公式但有些推导是错的只是碰巧测试用例通过。怎么辨别拿n从1到10的所有数组组合去随机验证一下就行。这道题的n很小暴力对拍几乎不费时间但能帮你建立对“题解”的批判性思维——这可能是刷题带给你最宝贵的习惯。