刷LeetCode刷到1588这道题大多数人第一反应是这不就是个简单的数组遍历题吗给一个数组求所有奇数长度子数组的和暴力三重循环直接梭哈AC了再说。但实话说这道题的价值被严重低估了——它表面上是个简单题实际上从三重暴力到前缀和再到数学公式恰好串起了一条完整的优化思维链是理解贡献法和求和次序交换的最佳入门素材。这篇文章我就围绕leetcode1588这题展开先把奇数长度子数组这个问题彻底讲透再带你从暴力一路走到O(n)的最优解。无论你是刚开始刷数组题的新手还是想把复杂度优化思路理顺的老手看完都能有收获。1. 题目到底在说什么先把奇数长度四个字磨清楚1.1 手工枚举一遍答案是怎么来的题目给一个整数数组比如arr [1, 4, 2, 5, 3]要你求的是所有长度为奇数的子数组的和全部加起来。什么叫子数组就是连续的一段。什么叫长度奇数就是1、3、5……这样的长度。我们手工枚举一下长度为1的子数组[1]、[4]、[2]、[5]、[3]和是 14253 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。这个例子是LeetCode官方的示例也最直观。你发现没有长度为偶数的子数组比如[1,4]、[4,2]、[1,4,2,5]通通不算数。1.2 最容易犯的混淆长度奇偶不等于下标奇偶新手最常见的一个错误理解是把奇数长度的子数组和下标为奇数/偶数的子数组搞混。子数组长度 右端点下标 - 左端点下标 1。要让它成为奇数本质上是要求左端点和右端点的下标奇偶性相同。为什么因为R - L 1是奇数意味着R - L是偶数也就是R和L同奇同偶。这个结论非常关键后面优化到O(n)全靠它。举例验证子数组[4,2,5]在原数组里下标是 1 到 3L1奇数、R3奇数长度 3 - 1 1 3奇数。子数组[2,5]是下标 2 到 3L2偶数、R3奇数长度 3 - 2 1 2偶数不算。所以这道题换个说法就是统计所有左、右端点奇偶性相同的连续区间之和。1.3 题目的坑不在难度而在能不能想到更优数组长度n在LeetCode上的约束其实很小老版本的题目甚至n 100都能过。所以很多人三重循环AC之后就走了根本不会去想这题还有没有更漂亮的解法。但恰恰是这种暴力也能过的题最容易掩盖思维上的漏洞。你想想如果n改成 10^5三重循环直接超时这时候你还能不能写出解法如果不能说明你对前缀和、贡献法这些基础工具的理解还是停留在背模板阶段。接下来我从最笨的解法开始一步步把这道题的优化路径完整走一遍。2. 第一版三重暴力循环先把逻辑做对2.1 枚举起点、终点再累加区间和最符合人类直觉的做法是三重循环。第一重枚举子数组起点i第二重枚举终点j第三重把i到j之间的元素加一遍。如果长度是奇数就把这个区间和累加到答案里。int sumOddLengthSubarrays(vectorint arr) { int n arr.size(); int ans 0; for (int i 0; i n; i) { for (int j i; j n; j) { if ((j - i 1) 1) { // 长度是奇数 for (int k i; k j; k) { ans arr[k]; } } } } return ans; }这里我用位运算(j - i 1) 1判断奇偶结果为1说明最低位是1也就是奇数。比写% 2 ! 0稍微省一点点开销更主要是代码干净。2.2 手动验证一次确保枚举无遗漏用arr [1,4,2,5,3]跑一遍逻辑i0时j从0到4长度奇数的是j0, 2, 4分别对应[1]、[1,4,2]、[1,4,2,5,3]i1时j1, 3对应[4]、[4,2,5]i2时j2, 4对应[2]、[2,5,3]i3时j3对应[5]i4时j4对应[3]把这些区间和加起来正好是58。说明逻辑正确。2.3 暴力的复杂度到底能不能接受三重循环最内层循环长度平均大约是 n/3整体复杂度 O(n^3)。n100时大约执行100万次加法现代计算机毫无压力但n10^4时就是10^12次直接超时到姥姥家。LeetCode上这题的旧版本确实给了很小的数据范围导致暴力能过。但这不代表暴力是个好解法。我自己的习惯是一道题暴力过了只是做题把优化路径走通才是学题。所以继续往下。3. 第二版前缀和把三重循环压成两重3.1 频繁算区间和最笨的地方在哪刚才的暴力有一个明显的浪费枚举(i, j)之后第三重循环从头加到尾。实际上在枚举j的过程中区间和是不断累加的——[i, j]的和完全可以在j变化时递推出来根本不需要每次都从i加到j。但更通用、更值得掌握的做法是前缀和。预处理一个数组pre让pre[k]表示原数组前k个元素的和那么区间[i, j]的和就是pre[j1] - pre[i]一次减法搞定。3.2 前缀和版本的代码int sumOddLengthSubarrays(vectorint arr) { int n arr.size(); int ans 0; vectorint pre(n 1, 0); for (int i 0; i n; i) { pre[i 1] pre[i] arr[i]; } for (int i 0; i n; i) { for (int j i; j n; j) { if ((j - i 1) 1) { ans pre[j 1] - pre[i]; } } } return ans; }两层循环枚举所有子数组区间和用前缀和 O(1) 得到总复杂度 O(n^2)空间 O(n)。如果把pre就地改成原数组原地前缀和空间还能压到 O(1)不过可读性会差一点。3.3 为什么前缀和不只是忘掉也没关系的小技巧前缀和解决的核心问题是频繁查询静态区间和。你可以把它理解成给一条街上的每家每户编号然后记录下从街头到每一家门前的累计人口。想知道任意一段街区住了多少人只需要用两个累计值相减。不用每一段都重新数一遍。这道题里暴力解法每次枚举区间都重新数前缀和把数人的时间从 O(长度) 降到了 O(1)。这个思想在大量数组题里都会用到比如求连续子数组和等于k的个数、二维矩阵区域和等等。不过呢O(n^2)仍然不是终点。两重循环说白了还是在枚举子数组。而枚举子数组这件事本身在数据量大起来以后依然是个奢侈行为。下一节我们换个思路彻底跳出枚举区间的框架。4. 真正的O(n)别再枚举子数组了数一数每个元素被加了几次4.1 交换求和次序贡献法的核心回到最原始的定义我们要把所有奇数长度子数组的和加起来。假设答案是ans那么它可以写成ans Σ(每个子数组的和)而每个子数组的和又是它内部所有元素相加。所以把所有子数组展开后ans实际上是所有元素被累加若干次的总和。换句话说对于一个固定位置i上的元素arr[i]它会被多少个奇数长度子数组包含假设这个次数是cnt[i]那么arr[i]对最终答案的贡献就是arr[i] * cnt[i]。于是问题变成求cnt[i]。这个方法叫贡献法也有人叫算贡献或者每个元素独立统计。核心就是交换求和次序——先别看有多少个子数组而是看每个元素出现在多少个子数组里。这比枚举所有子数组聪明得多。4.2 包含 arr[i] 的子数组总共有多少个先不要管长度奇偶。一个子数组要包含arr[i]它的左端点L必须满足0 L i右端点R必须满足i R n-1。左端点有i1种选择0到i右端点有n-i种选择i到n-1。左右端点独立选择所以包含arr[i]的子数组总数是(i 1) * (n - i)这个公式本身很有用就算不解决这道题很多子数组计数问题也能用它兜底。4.3 这总数里奇数长度子数组占多少接下来就是用长度奇数 L和R同奇偶这个结论的地方了。把左端点分成奇数下标和偶数下标两组右端点也分成奇数、偶数两组。那么同奇组合数 左边奇数个数 × 右边奇数个数同偶组合数 左边偶数个数 × 右边偶数个数cnt[i]就是这两个乘积之和。很多官方题解给出的是这样一个式子cnt[i] ((i 1) / 2) * ((n - i) / 2) ((i 2) / 2) * ((n - i 1) / 2)这里的/是整数除法。式子看着唬人其实本质就是奇数乘奇数偶数乘偶数分开算而已。但我想告诉你一个更漂亮的规律在所有包含arr[i]的(i1)*(n-i)个子数组中奇数长度的子数组数量恰好是总数的一半向上取整。也就是cnt[i] ((i 1) * (n - i) 1) / 2仍然使用整数除法。为什么要向上取整直觉解释是原数组下标从0开始左端点的候选下标里偶数永远不会比奇数少右端点的候选里奇偶数量要么一样多要么也偏向偶数一侧取决于i的奇偶但最坏情况也只是差1。在同奇同偶这组比一奇一偶这组少的偏差最多只有1所以奇数长度子数组数量要么正好一半要么多出1个。举个例子验证。arr [1,4,2,5,3]n 5i0包含它的子数组总数(01)*(5-0)5cnt (51)/2 3。三个奇数长度子数组是[1]、[1,4,2]、[1,4,2,5,3]正确。i1总数2*48cnt (81)/2 4。包含4的奇数长度子数组有[4]、[4,2,5]、[1,4,2]、[1,4,2,5,3]正好4个。i2总数3*39cnt (91)/2 5。五个子数组分别是[2]、[2,5,3]、[1,4,2]、[4,2,5]、[1,4,2,5,3]。这个总数取半向上取整的结论比背四段公式好记多了而且直接就是一个一行公式。4.4 O(n)代码长什么样int sumOddLengthSubarrays(vectorint arr) { int n arr.size(); int ans 0; for (int i 0; i n; i) { int cnt ((i 1) * (n - i) 1) / 2; ans arr[i] * cnt; } return ans; }整个函数只有一层循环时间复杂度 O(n)空间复杂度 O(1)。我第一次写出这个版本的时候自己都有点不敢相信——前面又是三重循环又是前缀和最后居然可以压缩成这么几行。但数学上它是严谨的而且我拿各种测试用例验证过[1]答案是1。公式算出来cnt1贡献1*11。[1,2]所有奇数长度子数组是[1]和[2]答案3。公式i0贡献1i1贡献2总数3。[10,20,30]奇数长度子数组有[10]、[20]、[30]、[10,20,30]答案120。公式i0cnt2贡献20i1cnt2贡献40i2cnt2贡献60总数120。[1,4,2,5,3]答案58和官方示例一致。4.5 两个公式为什么等价拆开看也没那么玄如果你把官方那个四项公式展开再用leftOdd (i1)/2、leftEven (i2)/2这类写法带进去在整数除法的规则下它最终会收敛到((i1)*(n-i)1)/2。这里面的关键是奇数下标个数和偶数下标个数的差左侧最多为1右侧也最多为1二者相乘后同奇偶的组合数要么等于总数一半要么多1。而多1的情况只会出现在总数本身为奇数的时候。所以下次再看到别人题解里贴出那一长串公式别慌它和这一行公式是同一个东西只是表达方式不同。选哪个写进代码我选短的因为越短的代码越不容易写错越容易review。5. 从这题带走的东西贡献法的通用套路与变式5.1 一个反转练习如果改成偶数长度子数组怎么办掌握了贡献法我们顺手可以做一个变式求所有偶数长度子数组的和。同样的思路只要把向上取整改成向下取整cnt[i] ((i 1) * (n - i)) / 2原因很简单包含arr[i]的子数组总数是(i1)*(n-i)其中奇数长度占一半向上取整那剩下的偶数长度就占一半向下取整。二者加起来正好是总数。代码只需要改一行int sumEvenLengthSubarrays(vectorint arr) { int n arr.size(); int ans 0; for (int i 0; i n; i) { int cnt ((i 1) * (n - i)) / 2; ans arr[i] * cnt; } return ans; }拿[1,2]验证偶数长度子数组只有[1,2]和是3。公式i0cnt(2)/21贡献1i1cnt(2)/21贡献2总数3。完美。这个变式很值得自己动手跑一遍你会更透彻地理解总数和奇偶占比的关系而不是死记公式。5.2 贡献法还能用在哪从1588看向更难的题每个元素被多少个合法区间包含这个思路向上可以迁移到不少经典题。比如LeetCode 907题子数组的最小值之和要求所有子数组的最小值加起来。暴力枚举所有子数组复杂度太高但换个角度每个元素arr[i]作为最小值被多少个区间包含只要找到左边第一个比它小的位置和右边第一个比它小的位置就能算出arr[i]作为最小值的区间个数然后累加arr[i] * 个数。这就是标准的单调栈 贡献法。再比如很多子数组乘积、子数组异或和的变种题只要目标函数具备可加性或可分解性大概率能往贡献法上靠。判断标准就一句话能不能把枚举区间转化为统计每个位置被包含的次数5.3 刷简单题的正确姿势把复杂度梯度走完说句可能有点得罪人的话如果刷1588这题只满足于三重循环AC那你错过的东西比这题本身多得多。我习惯的做法是拿到一道题先写最暴力的版本确认思路再想办法降一维复杂度最后尝试能不能压到理论最优。这个过程不只是在解一道题而是在练复杂度敏感。有些题目数据范围很小暴力能过但面试官追问一句还能怎么优化的时候你脑子里如果没有前缀和、没有贡献法这些工具箱临时想是想不出来的。1588是个绝佳的练习素材因为它短小精悍把暴力、前缀和、数学推导三种层次放在同一个题目里你完全可以用它来检验自己对基本算法的掌握程度。最后提一句编码细节在ans arr[i] * cnt这一步如果数组元素很大、数组很长中间结果可能超过int范围建议用long long承接LeetCode这题的答案在官方约束下int够用但自己扩展测试时留个心眼总是好的。