offer_64.md

面试题64. 求1+2+…+n

求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

对每一个孩子，检查是否存在一种方案，将额外的 extraCandies 个糖果分配给孩子们之后，此孩子有 最多 的糖果。注意，允许有多个孩子同时拥有 最多 的糖果数目。

示例1:

输入： n = 3
输出： 6

示例2:

输入： n = 9
输出： 45

---

解法一：递归
思路：

常见的逻辑运算符有三种，即 “与 &&&& ”，“或 ||∣∣ ”，“非 !! ” ；而其有重要的短路效应，如下所示：

if(A && B) // 若 A 为 false ，则 B 的判断不会执行（即短路），直接判定 A && B 为 false if(A || B) // 若 A 为 true ，则 B 的判断不会执行（即短路），直接判定 A || B 为 true

本题需要实现 “当 $n = 1$ 时终止递归” 的需求，可通过短路效应实现。

n > 1 && sumNums(n - 1) // 当 n = 1 时 n > 1 不成立 ，此时 “短路” ，终止后续递归

class Solution {
    public int sumNums(int n) {
        boolean flag = n > 0 && (n += sumNums(n - 1)) > 0;
        return n;
    }
}

复杂度分析：

• 时间复杂度：$O(n)$，递归函数递归 $n$ 次，每次递归中计算时间复杂度为 $O(1)$，因此总时间复杂度为 $O(n)$。
• 空间复杂度：$O(n)$，递归函数的空间复杂度取决于递归调用栈的深度，这里递归函数调用栈深度为 $O(n)$，因此空间复杂度为 $O(n)$。