64. 求1+2+…+n【短路】

1. 问题

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

示例 1：

输入: n = 3
输出: 6

示例 2：

输入: n = 9
输出: 45

限制：

• 1 <= n <= 10000

2. 标签

• 位运算

• 递归

3. 解法

递归时一般都会使用条件判断语句来决定递归的出口，由于题目限制无法使用，我们可以使用逻辑运算符的短路性质来决定递归的出口。

3.1 Java

class Solution {
    public int sumNums(int n) {
        /**
         * A && B
         * A: n > 0
         * B: n += sumNums(n - 1)
         * 可以将判断是否为递归的出口看作 A 部分
         * 将递归的主体函数看作 B 部分
         *  1. 如果不是递归出口，也就是 n > 0，那么返回 True，继续执行 B 部分，进行递归
         *  2. 如果是递归出口，也就是 n == 0，那么返回 False，短路，不再执行 B 部分，结束递归
         */
        boolean flag = n > 0 && (n += sumNums(n - 1)) > 0; // 这里其实 >0 <0 ==0 都可以，只是为了凑出一个表达式然后语法报错
        return n;
    }
}

3.2 Kotlin

？

3.3 复杂度分析

• 时间复杂度 O(n) ：递归函数总共递归了 n 次，每次递归中计算操作的时间复杂度为 O(1)，因此总时间复杂度为 O(n)。

• 空间复杂度 O(n) ：递归函数的空间复杂度取决于递归调用栈的深度，这里深度为 O(n)。

4. 参考

• https://leetcode-cn.com/problems/qiu-12n-lcof/
• https://leetcode-cn.com/problems/qiu-12n-lcof/solution/qiu-12n-by-leetcode-solution/
• https://leetcode-cn.com/problems/qiu-12n-lcof/solution/mian-shi-ti-64-qiu-1-2-nluo-ji-fu-duan-lu-qing-xi-/