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

约 6 分钟
文章信息 7 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 腾讯 字节
标签
字符串 回溯

题目描述

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

image-20260928225128559

image-20260928225128560

题意分析

将整个数字字符串按顺序切成至少三个非负整数，使第三项起的每一项都等于前两项之和。每项必须不超过 2^31-1，除了单独的 0，数字片段不能有前导零。

前两项可以自由选择，不要求从 0、1 开始；一旦确定前两项，后续每一项的数值就被唯一确定。找到任意合法拆分即可返回，没有则返回空列表。

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

核心思路

[!blue]

回溯状态由 idx 和 path 组成：idx 是下一个尚未使用的字符位置，path 保存已经选好的数字。每次从 idx 开始向右延长当前片段，用 value = value * 10 + 当前数字 构造候选值，再尝试把它放入序列。

前两项只要满足前导零和数值范围约束，都可以继续尝试。已有至少两项后，下一项必须等于它们的和 expect：

  • value < expect 时，当前片段还太小，继续纳入后面的数字。
  • value == expect 时，才可以选中当前片段并递归处理剩余字符串。
  • value > expect 时，继续延长只会让数值更大，可以直接结束当前循环。

如果片段首字符是 0，只允许取这一位；如果 value 超过 2^31-1，更长片段也不合法，立即停止。构造值和计算前两项之和都使用 64 位整数，避免先在 32 位运算中溢出后再判断。

选择一个数字后递归尝试后缀：成功就直接返回，保留整条 path；失败则删除刚加入的数字，恢复到本次选择之前，再试其他切分。只有到达字符串末尾且已经选出至少三项，才算成功。所有分支都失败时，每次选择都已撤销，入口返回的路径自然为空。

解题步骤

  1. 从下标 0 和空路径开始搜索。到达字符串末尾时，检查路径长度是否至少为 3。
  2. 从 idx 向右枚举片段末尾，先排除多位前导零，再逐位构造 value 并检查整数上限。
  3. 已有两项时，将当前值与前两项之和比较，分别继续扩位、允许选择或结束循环。
  4. 将合法候选加入 path，从下一字符递归。成功立即返回，失败删除末尾候选后继续尝试。
  5. 返回第一次找到的完整路径；不存在合法拆分则返回空列表。连续的零可以各自作为独立的数，但不能合成带前导零的多位数。

代码实现

class Solution {
    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 {
    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
}

复杂度分析

设字符串长度为 n，单个合法整数最多有 L = 10 位。

  • 时间复杂度：$O(nL^2)$。前两个数各至多有 L 种长度，确定它们后，后续每项都由相邻两项之和决定，验证剩余字符串需要 $O(n)$。这里 L 是常数，不是对全部切分方式进行指数枚举。
  • 空间复杂度：$O(n)$，路径与递归栈都可能线性增长；全零字符串可以拆成 n 个独立的零。

关键点总结

[!green]

  • 自由选择集中在前两项，后续按确定的和匹配，大幅减少回溯分支。
  • 片段变长时数值不会减小，所以超过预期或整数上限后可以直接停止。
  • 成功时保留路径，失败时撤销选择，最后才能返回完整答案或空列表。

易错点总结

[!yellow]

  • 只检查是否用完整个字符串：只有一项或两项仍不满足要求，必须至少有三项。
  • 当前值小于预期就停止：继续扩展当前片段仍可能达到预期，应继续读取数字。
  • 一看到 0 就拒绝：单独的零合法，禁止的只是多位数字以零开头。
  • 转换为整数后才判断前导零：转换会丢失原始写法，应检查片段起始字符和长度。
  • 先以 32 位整数计算和再转成 64 位：溢出会发生在转换之前，应先提升类型再相加。
  • 成功后也删除末尾数字：会破坏已经找到的答案，只有失败分支才回退。

相似题目

题目 难度 关联与区别
306. 累加数 中等 加法序列规则相同，本题要返回实际数列并受32位范围限制，原题只判断累加数是否存在。
415. 字符串相加 简单 较长数字段不能安全转整数时可用字符串加法核对后续项，但本题仍需遵守返回值范围。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/53597550
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！