微信公众号：路人zhang
扫码关注微信公众号

回复“面试手册”，获取本站PDF版

回复“简历”，获取高质量简历模板

回复“加群”，加入程序员交流群

回复“电子书”，获取程序员类电子书

当前位置： 算法 > 剑指offer > 剑指offer 64. 求1+2+...+n

剑指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完整版

剑指offer