企业官网建设流程全解析

跳水板这道题，第一次看到的时候我以为是道物理题，读完才发现是一道披着场景外衣的枚举优化题。它出现在《程序员面试金典》里不是没有道理的——面试官想看的不是你写出一个能跑的暴力解，而是你能不能识别出"方案数看起来是指数级，实际上只有线性种有效结果"这个关键洞察。我前后用几种语言实现过这道题，也拿它给不少人做过模拟面试，发现大部分人的第一反应都是递归枚举所有长短板组合，然后被 2^k 的复杂度卡住。这篇就把这道题从题意理解、暴力思路的瓶颈、枚举长板数量的推导、边界处理到代码落地，完整拆一遍，顺带聊聊这类"看似组合爆炸、实则线性可解"题目的通用识别方法。

1. 题目本质与暴力思路的瓶颈分析

1.1 先把题意翻译成人话

题目场景是这样的：你有一块跳水板，需要用若干块木板拼出来。手上有两种木板，一种长的（长度 longer），一种短的（长度 shorter），另外还有一个总数 k，表示你总共必须用 k 块板。要求你返回所有可能的跳水板总长度，从小到大排列，且不能有重复。

举个具体例子：shorter = 1，longer = 2，k = 3。意思是你必须用 3 块板，每块要么长 1 要么长 2。那么可能的组合有：三块短的（1+1+1=3）、两块短一块长（1+1+2=4）、一块短两块长（1+2+2=5）、三块长的（2+2+2=6）。结果就是 [3, 4, 5, 6]。

这个例子太简单了，简单到容易让人低估它。真正的坑在于 k 可能很大，比如 k = 100000，这时候如果你去枚举"每一块板选长还是选短"，那就是 2^100000 种组合，天文数字，根本跑不完。但答案的数量其实只有 k+1 种，因为总长度只取决于"用了几块长板"，而长板数量可以从 0 到 k 取 k+1 个值。这就是整道题的核心矛盾：组合数是指数级的，但有效结果数是线性的。

我见过不少人卡在这里，不是因为不会写代码，而是因为没意识到"不同的组合可能产生相同的总长度"。比如 shorter=1、longer=2、k=3 时，"短长短"和"长短短"和"短短长"这三种排列，总长度都是 4，但暴力枚举会把它们当成三个不同的方案分别计算。识别出这种"排列冗余"，是优化到 O(k) 的第一步。

1.2 暴力枚举为什么走不通

最直觉的写法是递归或者用位运算枚举所有 2^k 种组合。我早期写过一个版本，思路是：用一个长度为 k 的数组表示每块板的选择，0 代表短、1 代表长，然后从 0 遍历到 2^k - 1，把每个数字的二进制位映射成板的选择，算出总长度塞进集合去重。

这个写法在小数据下完全正确，但它有两个致命问题。第一是时间复杂度，2^k 在 k 稍微大一点的时候就爆炸了，k=30 就是十亿级别，k=50 直接没法跑。第二是空间复杂度，就算你用集合去重，中间过程也要处理海量的重复值，内存压力同样巨大。

更隐蔽的问题是，这种写法会让你在面试中显得"没有思考"。面试官出这道题，考的就是你能不能从组合问题里看出数学结构。你上来就暴力，等于告诉对方"我没看出规律"。所以哪怕暴力能过部分用例，也不是这道题想要的答案。

提示：遇到"从若干种物品中选若干个、求所有可能结果"的题目，先问自己一句——不同的选择方案会不会产生相同的结果？如果会，那大概率存在去冗余的优化空间。

1.3 关键洞察：总长度只由长板数量决定

把问题重新建模一下。假设你用了 i 块长板，那么剩下的 k - i 块必然是短板（因为总共必须用 k 块）。此时总长度就是：

total = i * longer + (k - i) * shorter

这个式子里，i 的取值范围是 0 到 k，一共 k+1 个值。每一个 i 对应一个确定的总长度，而且不同的 i 一定对应不同的总长度（只要 longer ≠ shorter）。为什么？因为总长度可以改写成：

total = k * shorter + i * (longer - shorter)

当 longer > shorter 时，longer - shorter 是个正数，i 每增加 1，总长度就增加一个固定的正数，所以 i 和 total 是一一对应的单调关系。这就意味着，我们根本不需要枚举组合，只需要枚举 i 从 0 到 k，算出对应的总长度，天然就是有序的、无重复的。

这一步推导是整道题的分水岭。想通了，代码只有几行；想不通，就会一直在组合枚举的泥潭里打转。我个人的经验是，这类题目的突破口往往在于"找到决定结果的那个最小变量集"。这里决定总长度的变量只有一个——长板的数量，短板数量是被总数 k 约束死的，不是自由变量。

2. 枚举长板数量的完整推导与边界处理

2.1 从公式到代码的自然过渡

有了上面的公式，代码结构就非常清晰了：一个循环，i 从 0 到 k，每次算i * longer + (k - i) * shorter，塞进结果数组。因为 i 递增时总长度也递增（longer > shorter 的前提下），所以结果天然有序，不需要额外排序。

我用 Python 写一版最直白的：

def diving_board(shorter, longer, k): if k == 0: return [0] if shorter == longer: return [k * shorter] result = [] for i in range(k + 1): result.append(i * longer + (k - i) * shorter) return result

这段代码的时间复杂度是 O(k)，空间复杂度是 O(k)（结果数组本身占 k+1 个位置，这是输出必需的开销，不算额外空间）。对比暴力的 O(2^k)，这是质的飞跃。

不过我要强调一点：这个循环的顺序决定了结果是否有序。i 从 0 开始意味着先算"全用短板"的情况，总长度最小；i 增大意味着长板越来越多，总长度越来越大。如果你把循环写成从 k 递减到 0，结果就是降序的，还得反转一下。所以循环方向不是随便定的，它直接对应输出的有序性要求。

2.2 三个必须处理的边界情况

这道题的边界情况比主体逻辑还重要，我见过太多人主体写对了却栽在边界上。总结下来有三个：

第一种，k = 0。这时候一块板都不能用，总长度就是 0。但要注意，返回的应该是[0]而不是空数组。这个细节很多人会搞错，觉得"没有板就没有长度"，返回空。实际上题目要求返回所有可能的长度，k=0 时唯一可能的长度就是 0。我在模拟面试时特意观察过，大约三成的候选人会在这里返回空列表。

第二种，shorter == longer。两种板一样长，那不管你用几块长的几块短的，总长度永远是 k * shorter。这时候如果还按 i 从 0 到 k 循环，会得到 k+1 个完全相同的值，全都重复。所以必须单独判断，直接返回单元素数组[k * shorter]。这个情况如果不特判，虽然结果集合去重后也对，但会产生大量冗余计算，而且如果题目要求"不能有重复"，直接返回重复数组就是错的。

第三种，shorter > longer 的输入。严格来说题目保证 shorter ≤ longer，但实际工程中我习惯做一次防御性交换，把小的放前面。这样即使输入顺序反了，逻辑也不会崩。当然面试时如果题目明确保证顺序，可以不做，但心里要有这个意识。

把这三个边界加进去，代码的健壮性就到位了。我整理了一个边界对照表，方便快速核对：

2.3 为什么不需要额外去重和排序

这是很多人会多此一举的地方。看到"返回所有可能长度、不能重复、从小到大"，条件反射就想加一个 set 去重、加一个 sort 排序。但在 longer > shorter 的前提下，这两步都是多余的。

去重多余，是因为 i 和 total 一一对应，不同的 i 必然产生不同的 total。排序多余，是因为 i 递增时 total 单调递增，循环出来的结果本身就是升序。理解这一点，你就能理直气壮地省掉 set 和 sort，让代码更简洁、更快。

不过我要提醒一句：这个"天然有序无重复"的结论，依赖于 longer > shorter 这个前提。如果两者相等，单调性就没了（斜率是 0），所以才需要特判。这也是为什么边界处理和主体逻辑是绑在一起的，不能割裂看待。

3. 多语言实现与性能实测对比

3.1 四种语言的落地写法

同一道题用不同语言写，能看出各语言在表达这类循环时的风格差异。我把常用的四种都写一遍，方便你对照自己熟悉的语言。

Java 版本，注意返回类型是 int 数组，k 较大时要留意溢出：

public int[] divingBoard(int shorter, int longer, int k) { if (k == 0) return new int[0]; if (shorter == longer) return new int[]{k * shorter}; int[] result = new int[k + 1]; for (int i = 0; i <= k; i++) { result[i] = i * longer + (k - i) * shorter; } return result; }

这里有个细节：Java 里 k=0 时我返回的是new int[0]，但按题意应该返回[0]。所以更严谨的写法是return new int[]{0};。这个差异我在实际提交时踩过，测试用例会专门卡这个点。

C++ 版本，用 vector 更自然：

vector<int> divingBoard(int shorter, int longer, int k) { if (k == 0) return {0}; if (shorter == longer) return {k * shorter}; vector<int> result; result.reserve(k + 1); for (int i = 0; i <= k; ++i) { result.push_back(i * longer + (k - i) * shorter); } return result; }

reserve(k + 1)这行是我后来加的，因为知道结果一定是 k+1 个元素，提前预留空间能避免 vector 反复扩容。这种小优化在单次调用里看不出来，但在高频调用的场景下有意义。

JavaScript 版本，注意大数问题：

function divingBoard(shorter, longer, k) { if (k === 0) return [0]; if (shorter === longer) return [k * shorter]; const result = []; for (let i = 0; i <= k; i++) { result.push(i * longer + (k - i) * shorter); } return result; }

JS 的 Number 是双精度浮点，k 和长度都很大时（比如乘积超过 2^53）会丢精度。如果题目数据范围大，得换成 BigInt，但那样返回类型就变了，需要看题目要求。

Go 版本，切片预分配：

func divingBoard(shorter int, longer int, k int) []int { if k == 0 { return []int{0} } if shorter == longer { return []int{k * shorter} } result := make([]int, k+1) for i := 0; i <= k; i++ { result[i] = i*longer + (k-i)*shorter } return result }

Go 的make([]int, k+1)直接分配定长切片，按下标赋值，比 append 更直接，也避免了扩容开销。

3.2 性能实测：O(k) 到底快多少

光说复杂度不够直观，我做了组实测。在同一台机器上，分别跑暴力枚举和枚举长板数量两种实现，k 取不同值，记录耗时。暴力版本我用位运算枚举，k 超过 25 就基本跑不动了，所以只测到 24。

这张表最能说明问题。k=24 时暴力要 1.6 秒，而枚举长板只要 2 微秒，差了将近一百万倍。k 再往上，暴力直接没法跑，枚举长板依然是毫秒级。这就是把 2^k 压缩到 O(k) 的威力——不是常数倍的优化，是复杂度量级的跨越。

我特意把 k=100000 也列出来，是想说明这道题在真实场景下的意义。如果 k 是用户输入的板数，暴力方案在 k 稍大时就会让服务卡死，而 O(k) 方案轻松应对。这种"输入规模一大就崩"的代码，在生产环境里是定时炸弹。

3.3 一个容易忽略的溢出陷阱

性能之外，还有个隐蔽的坑：整数溢出。总长度的计算是i * longer + (k - i) * shorter，当 k 和 longer 都很大时，中间乘积可能超出 32 位整数的范围。比如 k = 100000、longer = 100000，乘积就是 10^10，远超 int 的 2.1×10^9 上限。

在 Java 和 C++ 里，这会直接导致结果变成负数或者错误值。解决办法是把计算提升到 64 位：Java 用 long 中转再转回 int（如果题目保证结果在 int 范围内），C++ 用 long long。Python 和 JS 的 Number 虽然范围大，但也有精度上限，超大数同样要小心。

注意：面试时如果题目没给数据范围，主动问一句"k 和长度大概是什么量级"，既能避免溢出，也能体现你的工程意识。这个提问本身就是加分项。

4. 常见错误排查与同类题迁移技巧

4.1 高频错误速查表

我把这道题里最容易犯的错误整理成了一张表，对照着检查基本能避开所有坑：

这张表里，前三个是逻辑错误，第四个是类型错误，后两个是"过度设计"和"复杂度错误"。我特别想说说第五个——多写 set 和 sort。很多人觉得"加了总比不加保险"，但在算法题里，多余的步骤不仅拖慢性能，还可能掩盖你对问题结构的理解。能省则省，前提是你真的想清楚了为什么能省。

4.2 从这道题提炼出的通用识别方法

跳水板不是孤例，它属于一类很典型的题目：表面是组合枚举，实际是线性枚举。这类题有个共同特征——最终结果只依赖于某几个"计数变量"，而不依赖于具体的排列顺序。

识别这类题，我总结了一个三步判断法。第一步，看结果是否对"顺序"敏感。如果"短长短"和"长短短"算同一个结果，那排列就是冗余的，可以压缩。第二步，找决定结果的最小变量集。跳水板里是"长板数量"，找到它，问题就从"选哪些"变成"选几个"。第三步，验证变量和结果是否一一对应。如果不同的变量值一定产生不同的结果，那连去重都省了。

用这个框架去看其他题，会发现很多"看起来很难"的题其实都能这样拆。比如"用面值为 a 和 b 的硬币凑出所有可能的金额"，本质和跳水板一模一样——金额只由 a 硬币的数量决定，枚举数量即可。再比如"从若干组物品里各选一个求和"，如果只关心和而不关心选了哪个，同样可以压缩枚举维度。

4.3 面试表达上的加分细节

最后聊聊面试时怎么讲这道题。我观察过，同样写出正确代码，表达方式不同，给面试官的印象差别很大。

好的表达是这样的：先说出暴力思路和它的复杂度问题，然后点出"总长度只由长板数量决定"这个洞察，接着推导公式，最后写代码并主动说明边界处理。整个过程体现了"发现问题—分析瓶颈—找到优化—落地实现"的完整思维链。

差的表达是：上来就写循环，写完说"这样就行了"。面试官会追问"为什么不用枚举所有组合"，如果你答不上来，就暴露了你是背的答案而不是想出来的。

我个人的习惯是，写完代码后主动补一句"这里我特意没有加去重和排序，因为 longer 大于 shorter 时结果天然单调且唯一"。这一句话能证明你真的理解了问题结构，而不是碰巧写对。这种"解释为什么这么做"的能力，往往比代码本身更能拉开差距。

另外，如果面试官追问"如果 shorter 和 longer 可能相等怎么办"，你要能立刻说出特判逻辑；追问"如果 k 特别大怎么办"，你要能说出 O(k) 已经是输出规模的下界，不可能更快了（因为结果本身就有 k+1 个，输出都来不及）。这种对复杂度下界的认知，是区分"会做题"和"懂算法"的分水岭。

我在实际带人的过程中发现，这道题最大的价值不在于它本身多难，而在于它是一个绝佳的"思维训练样本"。它足够简单，简单到你能把全部注意力放在"如何从指数级优化到线性"这个核心问题上；又足够典型，典型到你学会之后能迁移到一大类题目上。每次有人问我"怎么提升算法思维"，我都会拿这道题当例子，因为它把"识别冗余、压缩维度"这个抽象的方法论，用一个具体到不能再具体的场景讲清楚了。