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

2021-09-19 HGNULB 约 8 分钟

文章信息 9 个分类 3 个标签

分类

LeetCode CodeTop 中等未解决 2-5 快手百度剑指 Offer 剑指 Offer（第 2 版）

题目描述

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

题意分析

要求算出 1 到 n 的连续整数之和，功能本身极其简单，真正的难点全在限制里：不许用乘除法，不许用 for、while 这类循环，不许用 if、switch、case 这类条件判断，也不许用三目运算符。

这些限制其实是在逐个封死常规通路。禁掉乘除，就是不让你套用高斯求和公式 n * (n + 1) / 2；禁掉循环，就是不让你从 1 累加到 n；禁掉条件判断和三目，就是不让你写显式的递归出口。剩下能用的只有加减法、赋值、位运算，以及函数调用本身。

于是问题的重心从「怎么算」变成了「在没有条件语句的前提下，怎么让一段重复执行的逻辑停下来」。约束里没有禁止递归，也没有禁止逻辑运算符，这两点就是留下的通道：递归提供重复，逻辑运算符提供终止。边界方面，n 至少为 1，所以不必考虑 n 为 0 或负数，但递归深度会随 n 线性增长，n 上限为一万时栈深度是可以接受的。

解法：递归 + 短路

核心思路

最自然的写法是 for (int i = 1; i <= n; i++) sum += i;，这在功能上无可挑剔，但循环被明令禁止。换成递归 return n == 0 ? 0 : n + sumNums(n - 1); 又踩中了条件判断和三目的禁区。瓶颈很清楚：递归本身是允许的，卡住我们的只是「递归出口必须用条件语句表达」这个惯性假设。

关键观察在于，逻辑与运算符 && 天然带有条件语义——A && B 在 A 为假时根本不会去求值 B，这个短路行为等价于一句「如果 A 不成立就什么都不做」的判断，但它是运算符而不是条件语句，完全绕开了限制。把递归调用塞进 && 的右操作数，就得到了一个不含任何 if 的递归出口。

于是不变量可以写成：调用 sumNums(n) 返回的一定是 1 加到 n 的和，其中局部变量 sum 初值为 n，只有当 n > 0 成立时才会被加上 sumNums(n - 1) 的结果。当 n 递减到 0 时，n > 0 为假，右侧的递归调用被短路掉，函数直接返回 sum = 0，递归自然收束；当 n 大于 0 时，sum = n + (1 + 2 + ... + (n - 1))，正是 1 加到 n。归纳法沿着 n 从 0 往上走，不变量在每一层都成立。

解题步骤

第一步，在函数入口把局部变量 sum 初始化为 n。这一步同时承担了两件事：既是本层要贡献的那个加数，也是 n 为 0 时的返回值 0，一个变量把「递归体」和「递归出口」合并了，从而不需要再写额外的分支去区分两种情况。

第二步，构造表达式 n > 0 && (sum += sumNums(n - 1)) > 0。左操作数 n > 0 是真正的递归终止条件，写成比较表达式而不是 if 语句，是因为题目禁的是条件语句而不是比较运算符。

第三步，把递归调用写在 && 的右侧。这样安排的原因是短路规则只对右操作数生效：n 为 0 时左侧为假，整个表达式立即定值为假，右侧的 sumNums(n - 1) 连求值机会都没有，递归就此打住，不会无限下探到负数。

第四步，把 (sum += sumNums(n - 1)) 的结果再和 0 做一次比较。这是纯粹的类型适配：Java 的 && 两侧必须是布尔值，而 sum += ... 的结果是整型，补上 > 0 才能通过编译。这个比较的真假无关紧要，重要的是赋值这个副作用已经发生了。

第五步，把整个表达式赋给一个用不到的布尔变量 unused。Java 不允许把一个表达式单独当作语句，必须让它出现在赋值或方法调用的位置，这个变量存在的唯一意义就是给表达式找个合法的落脚点。Go 版本因为 && 右侧不接受带副作用的赋值表达式，改用一个立即执行的匿名函数把 sum += sumNums(n - 1) 包起来并固定返回 true，再用空标识符 _ 接住结果，思路和 Java 版完全一致。

第六步，返回 sum。此时 sum 要么是被短路后保留的初值 0，要么是本层的 n 加上下层递归累加出的结果。

以 n = 3 走一遍：进入 sumNums(3)，sum 初始化为 3，3 > 0 为真，于是求值右侧，调用 sumNums(2)；在 sumNums(2) 里 sum 初始化为 2，2 > 0 为真，调用 sumNums(1)；在 sumNums(1) 里 sum 初始化为 1，1 > 0 为真，调用 sumNums(0)；在 sumNums(0) 里 sum 初始化为 0，0 > 0 为假，短路生效，递归调用不再发生，直接返回 0。回溯时 sumNums(1) 得到 sum = 1 + 0 = 1 并返回 1；sumNums(2) 得到 sum = 2 + 1 = 3 并返回 3；sumNums(3) 得到 sum = 3 + 3 = 6 并返回 6，正是 1 + 2 + 3 的结果。全程没有出现任何循环、if 或三目。

代码实现

class Solution {
    // 使用逻辑与短路终止递归，避免显式判断。
    public int sumNums(int n) {
        int sum = n;
        boolean unused = n > 0 && (sum += sumNums(n - 1)) > 0;

        return sum;
    }
}

func sumNums(n int) int {
    // 使用逻辑与短路终止递归，避免显式判断。
    sum := n
    _ = n > 0 && func() bool {
        sum += sumNums(n - 1)
        return true
    }()

    return sum
}

复杂度分析

时间复杂度：$O(n)$，其中 n 为输入值。递归从 n 一路降到 0，每层只做一次比较和一次加法，层数与 n 成正比。

空间复杂度：$O(n)$。递归没有写成尾调用形式，回溯时还要在本层做加法，因此每一层的栈帧都必须保留到下层返回为止，栈深度等于递归层数。

关键点总结

把限制条件当成提示而不是障碍：题目每禁掉一样东西，就是在缩小答案的搜索空间，逐条排除之后剩下的往往只有一条路，这种「反向定位解法」的思路在脑筋急转弯类题目里通用。

逻辑运算符的短路是隐藏的条件语句：&& 天然表达「前提不成立就不执行」，|| 表达「前提成立就跳过」，把它们和递归组合就能构造出没有 if 的出口，这个技巧在防空指针、惰性求值等工程场景里同样常用。

让一个变量同时承担递归体与递归出口的语义：sum 初值取 n，使得 n 为 0 时天然返回 0，省掉了区分两种情况的分支，这种「用初值吃掉边界」的手法能显著简化递归代码。

注意语言差异带来的写法差异：Java 需要一个哑变量来让表达式合法，Go 则需要匿名函数来承载带副作用的赋值，同一个思路落到不同语言上要各自找合法的语法外壳。

面试视角：先主动复述题目禁掉了什么、还剩什么，再说明「递归 + 短路」是被剩下的唯一通路，然后当场推导出口为什么不会漏掉 n 为 0 的情况；如果面试官追问其它写法，可以补充位运算模拟乘法配合快速乘、或利用静态构造数组等偏门解法，但要指出短路递归才是这道题的标准答案。

易错点总结

把递归调用写在 && 左侧：(sum += sumNums(n - 1)) > 0 && n > 0 在 n = 3 时会一路递归到负数，短路永远不触发，直接栈溢出。

用 || 代替 && 且不调整条件：n > 0 || (sum += sumNums(n - 1)) > 0 在 n = 3 时左侧为真就短路了，右侧永不执行，返回值恒等于 n，答案变成 3 而不是 6。

把 sum 初始化为 0 而不是 n：n = 3 时每层只累加下层结果，从未把本层的 n 加进去，最终返回 0。

忘记 (sum += ...) > 0 里的括号：写成 sum += sumNums(n - 1) > 0 会先做比较再把布尔值参与加法，Java 直接编译不过，Go 同样类型不匹配。

递归参数写成 sumNums(n) 而不是 sumNums(n - 1)：n = 1 时参数永不减小，1 > 0 恒成立，无限递归到栈溢出。

在 Go 里直接写 _ = n > 0 && (sum += sumNums(n-1)) > 0：Go 的赋值不是表达式，编译期就会报语法错误，必须用匿名函数包一层。

为了「更清晰」而补上 if n == 0 { return 0 }：n = 5 虽然能算出 15，但用了被明令禁止的条件语句，属于答非所问，面试中会被直接判负。

用 n * (n + 1) / 2 一行返回：结果正确但同时踩了乘法和除法两条禁令，等于没做这道题。

忽略递归深度：如果把 n 放大到十万量级，n = 100000 会因为栈帧无法及时回收而抛出栈溢出错误，需要提前说明该解法受调用栈深度限制。

相似题目

题目	难度	考察点
67. 二进制求和	简单	手工模拟按位相加与进位，不依赖内置大数运算
70. 爬楼梯	简单	同为线性递推，但重点在记忆化消除重复子问题
118. 杨辉三角	简单	递推构造二维结果，考察下标边界而非终止条件
172. 阶乘后的零	中等	把连乘转化为因子计数，靠数学观察而不是硬算
202. 快乐数	简单	递推可能进入循环，需要用快慢指针判环来终止
231. 2 的幂	简单	用 `n & (n - 1)` 一次位运算取代循环判断
371. 两整数之和	中等	禁用加减号，改用异或与进位循环模拟加法
509. 斐波那契数	简单	递归会指数爆炸，必须改成滚动变量或矩阵快速幂
1006. 笨阶乘	中等	运算符按固定周期轮换，考察优先级处理与分组化简
面试题 08.06. 汉诺塔问题	简单	经典递归分解，重点在参数含义随层数交换
面试题 17.01. 不用加号的加法	简单	同样是「禁用某种运算符」的命题套路，出路在位运算
剑指 Offer 62. 圆圈中最后剩下的数字	简单	递推式需要自己推导，出口是规模为 1 的平凡情形