LeetCode 1588所有奇数长度子数组的和这道题我第一次刷是在准备面试的算法清单上看到的。给定一个正整数数组把所有长度为奇数的连续子数组找出来全部加起来听起来像是入门级的遍历题但真正动手写的时候才发现从暴力到前缀和再到 O(n) 的数学公式每一层都有值得琢磨的地方。这篇文章想把这套思路完整走一遍尤其是最后那种“贡献法”的推导保证你看完能给别人讲明白。做这道题不需要什么高深的算法基础只要懂数组和循环就能开始但如果你正在刷 LeetCode 热门100题、准备周赛或者刚接触前缀和与数学推导它都是很好的练手素材。题目本身不复杂适合作为从“会做”到“会想”的分界线。后面的内容会从最直观的枚举开始一步步压缩复杂度最后给出面试时最加分的 O(n) 解法并把容易踩的坑单独列出来。1. 题目到底在问什么从示例手算到边界条件1.1 先手动算一遍示例题目给了一个示例arr [1, 4, 2, 5, 3]要求返回所有奇数长度子数组的和。先说清楚“子数组”是什么。子数组必须是原数组中连续的一段比如 [1, 4, 2] 是但 [1, 4, 5] 不是因为 5 在数组里并不挨着 4。长度为奇数的子数组包括长度为 1、3、5 这些题目要求把所有这样的子数组的和再加起来。这个示例里长度为 1 的子数组有 [1]、[4]、[2]、[5]、[3]和为 1 4 2 5 3 15。长度为 3 的子数组有 [1,4,2]、[4,2,5]、[2,5,3]和分别为 7、11、10加起来是 28。长度为 5 的子数组只有一个就是整个数组 [1,4,2,5,3]和是 15。把 15 28 15得到 58这就是题目的输出。第一次做的时候我犯过一个理解上的小错误以为“奇数长度子数组”是某些固定位置的长度比如只取长度 1 和 3忘了长度 5 也是奇数。这种细节在题目描述里写得清楚但真上手写代码时很容易漏掉最长的那个子数组。还有一个容易混淆的点题目问的是“所有奇数长度子数组的和”不是“所有子数组的和的奇数部分”也不是“和为奇数的子数组”这两个方向完全不同审题时得先划清界限。1.2 边界条件与数据范围看题目给的范围arr.length 最大 100arr[i] 最大 1000。这个范围非常小所以哪怕写一个三重循环的暴力解法在真实判题环境里也能通过这也是这道题被很多人评为“新手友好”的原因。不过我要提醒一点LeetCode 的通过只是最低标准如果面试时只写出暴力解对方大概率会追问“能不能更快”这时候你需要能拿出前缀和最好还能写出 O(n) 的公式解法。所以后面的内容虽然包含暴力解但重点放在优化上。另外虽然这道题数据范围小、用 int 完全没问题但我在实际写代码时还是习惯用 long 累加。原因很简单如果面试官把数据范围改大到 10^5int 直接溢出你临时改类型容易慌不如一开始就写上 long这个习惯在很多区间求和题里都能帮你避开溢出陷阱。2. 解法一暴力枚举与前缀和优化先写对再写快2.1 三重循环暴力版零基础也能看懂的写法最直观的思路是枚举所有子数组的起点 i枚举所有终点 j只要长度是奇数就算一下区间和。算区间和的时候再写一个循环从 i 加到 j。这样一共三层循环时间复杂度是 O(n^3)。public int sumOddLengthSubarrays(int[] arr) { int n arr.length; int ans 0; for (int i 0; i n; i) { for (int j i; j n; j) { if ((j - i 1) % 2 1) { int sum 0; for (int k i; k j; k) { sum arr[k]; } ans sum; } } } return ans; }这段代码的正确性很容易验证它枚举了所有区间 (i, j)并且只累加奇数长度的区间和。对于新手来说这是最好的“兜底写法”因为它的逻辑和题目描述一一对应基本不会有思路上的偏差。但 O(n^3) 的问题在于当 n 到 1000 时循环次数就到十亿级别会超时。这道题 n 最大 100所以暴力能过可一旦面试官把范围改大这段代码就站不住了。暴力解的意义是帮你建立“枚举区间”这个基本框架后面的优化都是在它基础上做的。2.2 前缀和怎么把区间和变成 O(1)三重循环里最浪费的部分是内层那个求和的循环每个区间都要重新加一遍。前缀和就是提前算好“从开头到每个位置的总和”然后用减法直接得到任意区间的和。具体做法开一个 prefix 数组prefix[i] 表示 arr 前 i 个元素的和prefix[0] 0。那么区间 [i, j] 的和就是 prefix[j 1] - prefix[i]。举个例子arr [1, 4, 2]prefix [0, 1, 5, 7]区间 [1, 2] 的和就是 prefix[3] - prefix[1] 7 - 1 6也就是 4 2。用了前缀和之后枚举起点和终点仍然需要两层循环但区间求和变成了 O(1)整体复杂度降到 O(n^2)public int sumOddLengthSubarrays(int[] arr) { int n arr.length; int[] prefix new int[n 1]; for (int i 0; i n; i) { prefix[i 1] prefix[i] arr[i]; } int ans 0; for (int i 0; i n; i) { for (int j i; j n; j) { if ((j - i 1) % 2 1) { ans prefix[j 1] - prefix[i]; } } } return ans; }我打心底觉得前缀和是刷题路上必须养成直觉的基础工具。很多“求区间和”的题暴力写法都长一个样但只要一旦出现大量区间查询前缀和就是第一反应。1588 这道题用前缀和写出来思路清楚代码也少是面试时最稳妥的第二层答案。2.3 空间还能压到 O(1) 吗前缀和的缺点是额外开了一个和原数组等长的数组。其实在这道题里我们可以枚举起点 i然后让终点 j 从 i 开始逐渐右移同时维护当前窗口的和。每当窗口长度为奇数时把这个和累加到答案里。public int sumOddLengthSubarrays(int[] arr) { int n arr.length; int ans 0; for (int i 0; i n; i) { int currentSum 0; for (int j i; j n; j) { currentSum arr[j]; if ((j - i 1) % 2 1) { ans currentSum; } } } return ans; }这段代码的时间复杂度还是 O(n^2)但空间复杂度从 O(n) 降到了 O(1)。它在面试里是个不错的“加分细节”说明你不仅知道前缀和还知道滚动窗口可以省下数组。从实际运行来看n 很小的时候这种写法通常比前缀和还要快一点因为少了一次数组索引访问。这个版本已经足够应对绝大多数场景了。但 LeetCode 上很多高赞题解会直接给出 O(n) 的解法也就是每个元素只需要算一次贡献这就是下一节的核心内容。3. 解法二数学贡献法O(n) 的核心推导3.1 换个角度别求子数组求每个元素的“出场次数”前面所有解法都是“站在子数组视角”一个个子数组去求和。现在换一个完全不同的视角站在元素 arr[i] 的角度思考它到底会被多少个奇数长度子数组包含。如果知道这个次数直接让 arr[i] 乘以次数再加起来就是最终答案。这个思路有一个很形象的名字叫贡献法。它不直接回答“所有子数组的和是多少”而是回答“每个数字对最终答案贡献了多少”。这种视角在处理“所有子数组的某种统计量”问题时特别管用比如子数组的最小值、最大值、乘积等都可以套用。以示例数组 [1, 4, 2, 5, 3] 为例元素 1 在下标 0 的位置它会被哪些奇数长度子数组包含[1]、[1,4,2]、[1,4,2,5,3]一共 3 个。元素 4 在下标 1会被 [4]、[1,4,2]、[4,2,5]、[1,4,2,5,3] 这些包含数一数是 4 个。如果把每个元素的这个次数算出来乘以它本身最后全部相加应该还是 58。所以核心问题变成了如何快速算出第 i 个元素被多少个奇数长度子数组包含。这需要一点组合数学。3.2 包含 arr[i] 的子数组一共有多少个包含 arr[i] 的子数组起点可以在 i 的左边任意位置终点可以在 i 的右边任意位置。更精确地说起点可以选择 0 到 i 之间的任意下标一共 i 1 种选择。终点可以选择 i 到 n - 1 之间的任意下标一共 n - i 种选择。起点和终点各自独立选择所以包含 arr[i] 的连续子数组总数是 (i 1) * (n - i)。这是一个很好理解的乘法原理。但题目要的是“奇数长度”不是所有长度。在所有 (i 1) * (n - i) 个子数组里到底有多少个长度是奇数这里有一个非常漂亮的结论奇数长度的个数等于 ((i 1) * (n - i) 1) / 2。为什么是这个公式我把推导过程拆开讲因为这是整道题最值得理解的地方也是很多题解直接跳过、导致读者看不明白的部分。3.3 奇偶分类法的完整推导一个子数组的长度 终点下标 - 起点下标 1。要让这个值是奇数只需要“终点下标”和“起点下标”的奇偶性相同。因为如果两者同奇或同偶相减得到偶数再加 1 就变成奇数如果奇偶不同相减得到奇数再加 1 就变成偶数。于是问题变成在所有起点和终点的选择中起点偶数且终点偶数的情况有多少种起点奇数且终点奇数的情况有多少种两者相加。设 l i 1表示起点可选择的总数量。在从 0 到 i 的这些下标里偶数下标有 (l 1) / 2 个奇数下标有 l / 2 个。举个例子l 4也就是下标 0、1、2、3偶数下标是 0 和 2共 2 个(4 1) / 2 2奇数下标是 1 和 3共 2 个4 / 2 2完全吻合。同样的道理设 r n - i表示终点可选择的总数量。终点偶数下标有 (r 1) / 2 个终点奇数下标有 r / 2 个。所以奇数长度子数组的个数就是偶数起点个数 × 偶数终点个数 奇数起点个数 × 奇数终点个数代入计算((l 1) / 2) * ((r 1) / 2) (l / 2) * (r / 2)这个式子可以化简成 (l * r 1) / 2。我建议你自己拿几个不同的 i 验证一下比死记公式有用得多。比如 i 1l 2r 4套用简化公式(2 * 4 1) / 2 4和前面数出来的 4 个完全一致。3.4 最终 O(n) 代码与手算验证有了这个公式代码就非常简单了。遍历每个下标 i计算它被奇数长度子数组包含的次数乘以 arr[i]累加即可public int sumOddLengthSubarrays(int[] arr) { int n arr.length; int ans 0; for (int i 0; i n; i) { int l i 1; int r n - i; int count (l * r 1) / 2; ans arr[i] * count; } return ans; }拿示例数组完整算一遍arr [1, 4, 2, 5, 3]n 5。i 0l 1r 5count (5 1) / 2 3贡献 1 * 3 3。i 1l 2r 4count (8 1) / 2 4贡献 4 * 4 16。i 2l 3r 3count (9 1) / 2 5贡献 2 * 5 10。i 3l 4r 2count (8 1) / 2 4贡献 5 * 4 20。i 4l 5r 1count (5 1) / 2 3贡献 3 * 3 9。全部加起来3 16 10 20 9 58和题目输出一致。每次我给别人讲到这里都会强调一句推导公式时不要只看结论一定要亲手算一遍哪怕只算一个例子也能帮你深刻理解“为什么是向上取整而不是直接除以 2”。这个解法的时间复杂度是 O(n)空间复杂度是 O(1)已经是这道题的极限了因为你至少要把每个元素读一遍不可能再低。如果你用 Python 写甚至可以一行搞定class Solution: def sumOddLengthSubarrays(self, arr: List[int]) - int: n len(arr) return sum(arr[i] * ((i 1) * (n - i) 1) // 2 for i in range(n))3.5 为什么最后一个元素只贡献 3 次很多第一次接触贡献法的人容易产生一个疑问最后一个元素在整个数组的末尾它明明在子数组里出现的位置很受限为什么公式算出来是 3 次因为对于最后一个元素 arr[n-1]起点只能从 0 到 n-1一共 n 种终点只能固定在 n-1一共 1 种总子数组数是 n。在这些子数组里长度奇数的取决于起点下标是否为奇数所以大约是 n / 2 个或 (n 1) / 2 个。当 n 5 时起点是偶数 0、2、4 这三个对应的子数组长度分别是 5、3、1全是奇数所以正好 3 次。这种“首尾元素贡献少中间元素贡献多”的分布很有意思也正好印证了公式的合理性。中间的 2下标 2左右两边都能扩展它的总子数组数是 3 * 3 9奇数个所以贡献 5 次是所有元素里最多的。4. 解法三双指针与滚动窗口面试中的另一种表达4.1 用双指针枚举所有奇数长度窗口如果你觉得贡献法的数学推导在面试时容易紧张忘公式还有一种更“接地气”的实现思路枚举起点然后让窗口长度从 1 开始每次加 2用双指针维护当前窗口的和。这个方法的时间复杂度是 O(n^2)但它不需要前缀和数组也不需要复杂的奇偶分类逻辑非常直白。具体来说外层循环定下起点 start内层循环让 end 从 start 开始每次把窗口右边界扩展到 start len - 1其中 len 依次取 1、3、5直到超出数组范围。因为每次 len 增加 2窗口会一次性新增两个元素所以可以在循环中动态维护窗口和不必重新求和。public int sumOddLengthSubarrays(int[] arr) { int n arr.length; int ans 0; for (int start 0; start n; start) { int windowSum 0; for (int len 1; start len n; len 2) { if (len 1) { windowSum arr[start]; } else { windowSum arr[start len - 2] arr[start len - 1]; } ans windowSum; } } return ans; }这段代码里的细节是当 len 从 1 跳到 3 时需要新增的是 start 1 和 start 2 两个元素。写成代码就是 arr[start len - 2] 和 arr[start len - 1]。一开始我很不适应这种“跳跃式扩展”的写法总是想当然地写成一次加一个元素结果窗口和就错了。后来我给自己总结了一个规律窗口长度每次增加 2就要在原来和的基础上补两个位置千万别只补一个。4.2 为什么面试时可以先把 O(n^2) 版本讲给面试官我个人的刷题经验是面试遇到这道题不要一上来就甩 O(n) 公式除非面试官明确要求“能不能 O(n)”。更好的节奏是先说暴力解O(n^3)展示你能正确理解题意。提到用前缀和优化区间求和O(n^2)。然后说“我还能用数学方法做到 O(n)”再报出贡献法公式。这样既展示了扎实的代码能力又展示了对复杂度的敏感度。很多时候面试官其实不指望你一上来就给出最优解而是想看你能不能一步步通过“观察”和“分析”来逼近最优解。这道题的三种复杂度层级非常清晰正好是考察这种能力的理想题目。双指针滚动窗口这个版本最大的价值在于它不需要额外空间也不依赖数学公式适合在面试时作为“O(n^2) 的改进版”来讲。它和前面前缀和版本的区别是前缀和是“快速查任意区间”双指针是“维护一个正在滑动的窗口”两者解决的是同一类问题的不同侧面。4.3 从窗口视角看还有没有更快的可能如果你愿意再深挖一层会发现这道题也可以用“统计每个窗口长度为奇数的数量”来理解。但它本质上和元素贡献法是同构的只是观察角度不同。也有人在讨论区提出用差分数组或者二维前缀和来解但我个人觉得没必要。对于这种区间求和问题前缀和已经是比较优雅的工具了再加一层二维结构属于杀鸡用牛刀。真正的核心优化点只有一个不要傻乎乎地枚举所有子数组而是直接考虑每个元素的影响次数。一旦想明白这一点你的算法思维会有一次小小的升级。5. 常见问题与排查技巧实录5.1 为什么公式是 (l * r 1) / 2而不是 l * r / 2这是评论区出现频率最高的问题。原因在于奇偶分类法得到的表达式包含两个向上取整的项比如 ((l 1) / 2) * ((r 1) / 2) (l / 2) * (r / 2)化简之后是 (l * r 1) / 2。如果写成 l * r / 2当 l * r 为奇数时结果会少 1。我建议你在代码里果断使用 (l * r 1) / 2 这种写法因为整数除法本身是向下取整加 1 再除以 2刚好是把向上取整的效果“内置”进去了。这也是很多题解里代码看起来很短但你不理解时就会觉得像魔法的原因。5.2 为什么不能用子数组和为奇数作为筛选条件审题错误是另一个高频问题。题目要求“所有奇数长度子数组的和”意思是先选长度为奇数的子数组再把它们的和相加。关键在“奇数长度”不是“和为奇数”。有些读者读题时大脑自动过滤了“长度”两个字就会写出“只要子数组和是奇数就累加”结果跑出来的答案对不上示例。一个简单的自检方法拿 arr [1, 4, 2, 5, 3] 这个例子把所有子数组按长度分类画出来先标出奇数长度的再求和。你会发现 [1, 4, 2] 的和是 7是奇数但它被计入的原因是长度 3 为奇数而不是因为和是奇数。不要把因果搞反。5.3 溢出问题int 到底够不够原题里 n 最大 100arr[i] 最大 1000最大答案也就在百万级别int 完全够用。但如果你在练习时把数据范围改成了 10^5或者把元素范围放大到 10^9再使用 int 就会直接溢出。我个人的习惯是涉及累加和、乘法计数的题目结果变量一律用 long尤其当公式里出现 (i 1) * (n - i) 这种乘法时两个 int 相乘在极端情况下可能瞬间超出 int 范围。这道题虽然不会但养成长类型习惯能避免很多后续问题。5.4 调试技巧用暴力解做基准验证数学公式这是我刷题时最常用的一招。如果你新写了一个优雅的 O(n) 解法不要直接提交先在本地写一个朴素的暴力函数随机生成一些小数组把两个函数的输出逐一对比。Random rand new Random(); for (int t 0; t 1000; t) { int n rand.nextInt(10) 1; int[] arr new int[n]; for (int i 0; i n; i) { arr[i] rand.nextInt(10); } int expected bruteForce(arr); int actual sumOddLengthSubarrays(arr); if (expected ! actual) { System.out.println(error); } }这个方法帮我避免过无数“自以为对、实际有边界漏算”的情况。特别是像 1588 这种有数学公式的题一旦在推导过程中弄错了某个取整符号数组一大就立刻测出来。用暴力解做基准是验证所有优化解法正确性的通用手段不仅适用于这道题。5.5 这道题和 Cooley-Tukey、IEEE 1588 没有任何关系搜索的时候可能会发现1588 这个数字在计算机领域还对应着别的含义比如网络同步协议里的精确时间协议或者其他技术栈里的“1588 timer”。但 LeetCode 的 1588 就只是一个数组求和题不需要涉及任何网络协议或硬件知识不要被编号相同的其他技术名词带偏回归题目本身即可。另外如果你在刷题列表里看到“爱吃香蕉的狒狒”那类的二分查找题也不用把它们和这道题强行关联它们只是同时出现在热门题单里各自考察的能力点完全不同。1588 的核心能力是“遍历 数学观察”和二分答案没有关系。6. 实战复盘三种解法对比与我的个人体会把三种解法放在一张表里看复杂度演进就很清晰解法时间复杂度空间复杂度核心思路适合场景暴力枚举O(n^3)O(1)三重循环逐个子数组求和新手理解题意前缀和/滚动窗口O(n^2)O(1) 或 O(n)快速计算任意区间和面试基础解答数学贡献法O(n)O(1)统计每个元素的出次数追求最优解这三层解法不是孤立的它们之间有一条很自然的递进线索暴力太重是因为重复求和所以用前缀和前缀和虽然快但还是要枚举所有子数组所以干脆放弃“子数组”这个单位改用“元素贡献”这个单位于是得到 O(n)。从我刷题的实际感受来说第一次看到贡献法时我觉得它很聪明但并没有真正理解。后来我拿它去解了不少类似的题目比如所有子数组的最小值之和、所有子数组的乘积等才发现这种“跳出子数组、聚焦单一元素”的思路是可以泛化的思维框架。1588 是一个非常好的入门载体因为它的限制少、公式简单很适合用来建立这种直觉。给大家一个刷题建议不要因为数据范围小就只满足于暴力解也不要因为看了题解记住公式就觉得学会了。这道题的正确打开方式是先写暴力再写前缀和最后自己从“每个元素出现次数”的角度推一遍公式推不出来再看题解。整个过程走下来你对“区间求和类问题”的理解绝对会上一个台阶。最后分享一个小技巧如果你在面试中写出贡献法面试官很可能会追问“你怎么保证每个元素都恰好被统计一次”。这时候你可以回答因为每个奇数长度子数组都恰好只包含一组连续的元素所以当我们把每个元素在所有合法子数组中出现的次数相加时每个子数组的和会被完整拆解成单个元素的贡献之和不会被重复计算也不会被遗漏。这种解释方式比单纯背公式要有说服力得多。