微信公众号:路人zhang
网站救助计划

1.为阅读体验,本站无任何广告,也无任何盈利方法,站长一直在用爱发电,现濒临倒闭,希望有能力的同学能帮忙分担服务器成本


2.捐助10元及以上同学,可添加站长微信lurenzhang888,备注捐助网站倒闭后可联系站长领取本站pdf内容


3.若网站能存活下来,后续将会持续更新内容

当前位置: 算法 > 剑指offer > 剑指offer 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

题解

(递归) O(n)

递归求解替换 for 循环 1 + 2 + … + n 只不过需要将 if 替换掉,依据 A && B 的性质,如果 A 为 false,B 就不执行,如果 A 是 true,B 还要进行判断。同样的对于 A || B 依然有类似的性质,如果 A 是 true,B 就不执行,如果 A 是 false,B 还要进行判断。

因此我们可以用逻辑与 &&​ 运算符将 if 完美替换 if (n > 0) res += getSum(n - 1) -> n > 0 && (res += getSum(n - 1))

时间复杂度

递归 n 次,时间复杂度为 O(n)

时间复杂度

递归系统调用栈的空间为 O(n)

C++ 代码

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

Java 代码

class Solution {
    public int sumNums(int n) {
        int res = n;
        if (n > 0) {
            res += sumNums(n - 1);
        }
        return res;
    }
}

Python 代码

class Solution:
    def sumNums(self, n: int) -> int:
        res = n
        if n > 0:
            res += self.sumNums(n - 1)
        return res

本文由读者提供Github地址:https://github.com/tonngw


点击面试手册,获取本站面试手册PDF完整版