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

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. 参考

最后更新于