LeetCode 842. 将数组拆分成斐波那契序列

2021-08-11 HGNULB 约 9 分钟

文章信息 7 个分类 2 个标签

分类

题目描述

✅ 842. 将数组拆分成斐波那契序列

题意分析

输入是一个只含数字的字符串，长度不超过 200。要把它从左到右切成若干段，每段解释成一个整数，得到的数列必须满足后一项等于前两项之和。

合法性有三条硬约束：数列至少有 3 项；每个数都要落在 $[0, 2^{31} - 1]$ 内；除了单独的 "0"，任何数都不能以 0 开头。

题目只要求返回任意一个合法方案，不需要枚举全部方案，也不是计数题，因此一旦找到就可以立刻收工。

边界上要留意几点：字符串长度可能小于 3，必然无解；"0" 本身是合法数字，所以 "0000" 能切成四个 0；上界是 $2^{31} - 1$ 而不是 long 的范围，累加时容易在这里翻车。

解法：回溯枚举切分并约束下一数

核心思路

暴力做法是枚举所有切分方式，长度 $n$ 的串有 $2^{n - 1}$ 种切法，逐一验证。$n = 200$ 时完全不可行。

瓶颈在于绝大多数切分从第三个数开始就已经违反递推关系，却仍然被完整枚举到串尾。

关键观察是：序列一旦定下前两项 $f_0$ 和 $f_1$，后面每一项都被 $f_{k-1} + f_{k-2}$ 唯一确定，没有任何自由度可言。真正需要枚举的只有前两项的切法，共 $O(n^2)$ 种，剩下的部分是纯验证。

由此确定递归的不变量：backtrack(idx, path) 被调用时，path 已经是 num[0 .. idx - 1] 的一个合法拆分 —— 每一项都无前导零、都不超过 $2^{31} - 1$、且从第三项起满足递推。函数只需为剩余的 num[idx ..] 继续寻找合法拆分。这条约定既是正确性的依据，也直接给出了剪枝条件：当 path 已有两项时，当前片段的数值必须严格等于末两项之和。

解题步骤

准备路径列表 path，从 idx = 0 开始递归。path 全程只在末尾增删，配合上面的不变量，任何时刻它都是一个已验证的合法前缀。

在每一层，从 idx 向右逐位扩展候选片段，用 value = value * 10 + 当前数字 增量构建，避免每次重新做子串截取和字符串转数字。

扩展前先看前导零：若 i > idx 且 num[idx] == '0'，直接 break。判断放在扩展条件上而不是数值上，才能既允许单独的 "0"，又禁止 "01" 这种写法。

value 一旦超过 $2^{31} - 1$ 就 break。片段越长数值只增不减，后面不可能再合法，继续扩展纯属浪费。累加用 long，否则越界的那一刻数值本身已经被截断，判断就失效了。

若 path 已有两项，取 expect = path[末项] + path[次末项]，按三种情况分流：value < expect 时 continue，因为把片段再拉长数值会变大，有机会追上；value == expect 时把它加入 path 并递归；value > expect 时 break，数值单调递增，已经超了就永远追不回来。这三个分支正是把指数级搜索压成多项式的核心。

递归到 idx == num.length() 时返回 path.size() >= 3。两个条件缺一不可：只判到达串尾会漏掉「至少三项」，只判项数会漏掉「必须用完所有字符」。

递归失败后弹出刚加入的那一项，恢复现场，再尝试更长的片段。

以 num = "1101111" 走一遍：

idx = 0，取片段 "1"，value = 1，path 不足两项直接放入，path = [1]，递归到 idx = 1。

idx = 1，先取 "1"，path = [1, 1]，递归到 idx = 2。此时 expect = 2；片段 "0" 的值 0 小于 2，本该继续扩展，但下一步撞上前导零规则 num[2] == '0' 而 break，这一支失败，弹回 path = [1]。

idx = 1 继续扩展，取 "10"，value = 10，path = [1, 10]，递归到 idx = 3。expect = 11；片段 "1" 的值 1 小于 11 故继续扩展，"11" 的值 11 正好相等，放入得 path = [1, 10, 11]，递归到 idx = 5。这一层 expect = 21，从 "1" 扩到 "11" 都不足 21，扫到串尾仍未命中，返回失败；回到 idx = 3 再扩到 "111"，值 111 大于 11，break。整支失败，弹回 path = [1]。

idx = 1 再扩展，取 "110"，value = 110，path = [1, 110]，递归到 idx = 4。expect = 111；片段 "1" 值 1、"11" 值 11 都不足，扩到 "111" 时值 111 恰好相等，放入得 path = [1, 110, 111]，递归到 idx = 7。

idx = 7 等于串长，且 path 有 3 项，返回成功。最终答案 [1, 110, 111]，核对 $1 + 110 = 111$ 成立，三个数都在上界内、都无前导零。本题接受任意合法拆分，[11, 0, 11, 11] 同样正确，只是这套搜索顺序先撞上了前者。

代码实现

class Solution {
    // 一旦拿到前两个数，后续每个数就被 prev2 + prev1 唯一约束，搜索空间会迅速收敛。
    public List<Integer> splitIntoFibonacci(String num) {
        List<Integer> path = new ArrayList<>();
        backtrack(num, 0, path);
        return path;
    }

    private boolean backtrack(String num, int idx, List<Integer> path) {
        if (idx == num.length()) {
            return path.size() >= 3;
        }

        long value = 0;
        for (int i = idx; i < num.length(); i++) {
            if (i > idx && num.charAt(idx) == '0') {
                break;
            }

            value = value * 10 + (num.charAt(i) - '0');
            if (value > Integer.MAX_VALUE) {
                break;
            }

            int size = path.size();
            if (size >= 2) {
                long expect = (long) path.get(size - 1) + path.get(size - 2);
                if (value < expect) {
                    continue;
                }
                if (value > expect) {
                    break;
                }
            }

            path.add((int) value);
            if (backtrack(num, i + 1, path)) {
                return true;
            }
            path.remove(path.size() - 1);
        }

        return false;
    }
}

func splitIntoFibonacci(num string) []int {
    // 一旦拿到前两个数，后续每个数就被 prev2 + prev1 唯一约束，搜索空间会迅速收敛。
    path := make([]int, 0)
    const maxInt = int64((1 << 31) - 1)

    var dfs func(int) bool
    dfs = func(idx int) bool {
        if idx == len(num) {
            return len(path) >= 3
        }

        value := int64(0)
        for i := idx; i < len(num); i++ {
            if i > idx && num[idx] == '0' {
                break
            }

            value = value*10 + int64(num[i]-'0')
            if value > maxInt {
                break
            }

            if len(path) >= 2 {
                sum := int64(path[len(path)-1]) + int64(path[len(path)-2])
                if value < sum {
                    continue
                }
                if value > sum {
                    break
                }
            }

            path = append(path, int(value))
            if dfs(i + 1) {
                return true
            }
            path = path[:len(path)-1]
        }

        return false
    }

    dfs(0)
    return path
}

复杂度分析

时间复杂度：$O(n^3)$，前两项的切法共 $O(n^2)$ 种，每种情况下后续各项被递推唯一确定，验证要扫过剩余字符一遍，即 $O(n)$。上界虽是立方级，但两条数值剪枝会在绝大多数分支上提前 break，实测远低于此。

空间复杂度：$O(n)$，path 与递归栈的深度同为数列项数。全 0 串如 "0000" 会切出 $n$ 项，所以最坏就是线性。

关键点总结

先找出「自由度在哪里」再决定搜什么。本题看似要枚举所有切分，实际只有前两项自由，后面全是验证，认清这一点后指数级搜索直接塌成多项式。

剪枝要建立在单调性上。片段越长数值越大，value 与 expect 的三分支（小于继续、等于递归、大于停止）才成立；没有这层单调性就只能全枚举。

回溯的正确性靠一条清晰的「路径含义」约定。明确 path 是已验证的合法前缀之后，出口条件、剪枝条件、恢复现场三处的写法就都被这条约定唯一确定了。

数值类字符串题的边界永远在前导零和溢出这两处，写代码前先把 "0"、"0000"、"2147483648" 三个用例列出来，比写完再调试省时得多。

面试视角：面试官关注的不是你会不会写 DFS，而是能否说清「为什么只需枚举前两个数」和「为什么可以在 value > expect 时立刻 break」。把这两句话说明白，代码写不完也算答到了点上。

面试视角：这题和 306 累加数几乎同构，主动指出差异（306 只要判可行性、无 32 位上界）能体现你在做题型归类而不是背模板。

易错点总结

错误写法：前导零判断写成「片段首位是 0 就直接 break」。用 num = "0000" 试：单字符片段 "0" 本身合法，正确答案是 [0, 0, 0, 0]，一刀切会返回空列表。

错误写法：用 value == 0 && i > idx 判前导零。用 num = "0123" 试：片段 "01" 的数值是 1 不是 0，判断失效，会返回 [1, 2, 3]，而正确答案是空列表。

错误写法：用 int 累加 value。用 num = "2147483648" 试：int 在最后一位就溢出成负数，value > Integer.MAX_VALUE 永远不成立，越界数字被当成合法。累加必须用 long。

错误写法：求 expect 时不转 long，直接写 path.get(size - 1) + path.get(size - 2)。两项都接近 $2^{31} - 1$ 时相加溢出成负数，value < expect 恒不成立而 value > expect 恒成立，正确分支被剪掉。

错误写法：value < expect 时写 break 而不是 continue。用 "1101111" 试：path = [1, 110] 之后需要从 "1" 一路扩到 "111" 才追上 111，提前 break 会把唯一能走通的切法漏掉，返回空列表。

错误写法：value > expect 时写 continue 而不是 break。逻辑仍然正确，但数值单调递增意味着后面全是徒劳，剪枝失效后搜索回到指数级，长串直接超时。

错误写法：递归出口只判 idx == num.length() 就返回 true，漏掉 path.size() >= 3。用 num = "11" 试：会把两项的 [1, 1] 当成答案，正确答案是空列表。

错误写法：递归失败后忘记 path.remove(path.size() - 1)。残留元素会污染下一条分支的 expect，搜索在错误的递推基准上继续，最终返回的数列既对不上原串也不满足递推关系。

相似题目

题目	难度	考察点
93. 复原 IP 地址	中等	段数固定为 4，每段受 0 到 255 的范围约束
131. 分割回文串	中等	切分条件是每段自身回文，段与段之间互不牵连
139. 单词拆分	中等	合法性由词典决定，只问可行性，宜用记忆化
306. 累加数	中等	同为前两项定全局，但只返回布尔且无 32 位上界
873. 最长的斐波那契子序列的长度	中等	元素可跳选而非连续切分，转为哈希加动态规划