LeetCode 剑指 Offer 64. 求1+2+…+n

约 3 分钟
文章信息 9 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 剑指 Offer 剑指 Offer（第 2 版） 百度 快手
标签
位运算 递归 脑筋急转弯

题目描述

✅ 剑指 Offer 64. 求1+2+…+n

image-20261001230752595

题意分析

计算 1 + 2 + ... + n，但不能使用乘除法、for、while、if、else、switch、case 或三目运算符。需要在这些限制下完成重复累加，并让计算在适当位置停止。

解法：递归 + 短路

核心思路

[!blue]

求和满足 f(n) = n + f(n - 1)，且 f(0) = 0。递归可以代替循环，但仍需要出口；这里利用逻辑与 && 的短路规则：只有左侧为真，右侧才会求值。

每层先令 sum = n，再计算 n > 0 && 右侧表达式。n > 0 时，右侧递归求前 n - 1 项并累加；n == 0 时，右侧完全不执行，直接返回初始值 0。返回到上一层后，再把该层的 n 加上，逐层得到目标和。

&& 两侧必须是布尔值。Java 用 (sum += sumNums(n - 1)) > 0，先累加再比较；Go 用立即调用的函数完成累加并返回 true。最终布尔值不参与答案，但求值过程中对 sum 的修改必须保留。

解题步骤

  1. 用当前 n 初始化本层的 sum。
  2. 把 n > 0 放在 && 左侧，递归调用和累加放在右侧。
  3. 正数层先等待 sumNums(n - 1) 返回，再将它加到 sum；零层直接短路。
  4. 返回本层 sum。

代码实现

class Solution {
    // 使用逻辑与短路终止递归，避免显式判断。
    public int sumNums(int n) {
        int sum = n;
        // n 为零时短路终止；比较结果只为满足布尔类型，右侧累加仍会执行。
        boolean unused = n > 0 && (sum += sumNums(n - 1)) > 0;

        return sum;
    }
}

func sumNums(n int) int {
    // 使用逻辑与短路终止递归，避免显式判断。
    sum := n
    // n 为零时不调用右侧函数；函数在完成累加后返回布尔值。
    _ = n > 0 && func() bool {
        sum += sumNums(n - 1)
        return true
    }()

    return sum
}

复杂度分析

  • 时间复杂度：$O(n)$，从 n 递归到 0，每层做常数次操作。
  • 空间复杂度：$O(n)$，递归调用栈有 n + 1 层。

关键点总结

[!green]

  • 短路提供递归出口，关键是先求左侧条件。
  • 丢弃的是布尔结果，不是右侧表达式执行的加法。
  • 每层使用自己的局部 sum，返回值已经包含这一层及更小整数的总和。

易错点总结

[!yellow]

  • 把 Java 的短路逻辑与换成非短路按位与，会在零之后仍继续递归。
  • 删除看似未使用的布尔表达式，会把求和变成只返回 n。
  • 递归减一后没有加回当前 n，会漏掉本层贡献。
  • 将递归放在 && 左侧会先执行递归，无法靠右侧条件阻止无限调用。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/79773922
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！