AcWing 84. 求1+2+…+n

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 84. 求1+2+…+n 原题链接简单

作者：

cornerCao , 2019-01-17 15:18:50 , 所有人可见 , 阅读 10172

114

64

算法

(递归) $O(n)$

最直接的想法就是用递归，sum(n) = n+sum(n-1)，但是要注意终止条件，由于求的是1+2+…+n的和，所以需要在n=0的时候跳出递归，但是题目要求不能使用if,while等分支判断，可以考虑利用&&短路运算来终止判断。

时间复杂度分析：递归，复杂度为$O(n)$。

C++ 代码

class Solution {
public:
    int getSum(int n) {
        int res = n;
        (n>0) && (res += getSum(n-1));//利用短路运算终止递归
        return res;
    }
};

27 评论

knewbie 2022-09-17 16:24

学到了，tql！！
另外发现可以把关键的那一句和return直接放在一起写。利用逗号表达式即可

return ((n>0) && (res += getSum(n-1)), res);

FITINGQG 2022-11-26 15:14

orz

志秋世 2021-12-23 17:11

短路好评

acwing_3914 3个月前

666

lsxstart 5个月前

有想法，牛逼

doilion 9个月前

tql

卯花之佐久夜姬 2023-11-11 10:08

太妙了，第一次知道短路运算！

晓月兮清风 2023-10-06 10:28

#酱紫不行吗

class Solution {
public:
    int getSum(int n) {
        if (n == 0) return 0;
        return getSum(n - 1) + n;
    }
};

就你也想和老爹过过手吗 2023-10-07 14:47

不能用if

达不溜达 2023-07-30 20:41

用短路运算太帅了

15082154025 2023-03-10 14:26

# amz

般若巴麻空 2023-01-24 22:22

tql

mkkk123fromage 2023-01-10 16:10

orz

种花家的老六 2022-07-28 14:17

为什么不能用等差数列求和公式呢？

I_can_do_wonders 2022-08-12 22:04

因为包含乘法除法啊！！！

种花家的老六 2022-08-13 10:27 回复了 I_can_do_wonders 的评论

哦

北冥有好多鱼 2022-03-09 20:47

大佬tql

小霸王学习机_6 2022-01-25 21:10

tql

MEDIC 2022-01-22 23:49

是挺短的

DiveBackInTime 2021-07-16 15:09

Markdown

#####test
hello

#end
GOODBYE!

胖金哥 2021-03-04 13:01

tql

ims 2021-02-21 22:49

大佬

今天也很菜 2020-12-23 17:27

tql

App 内打开

AcWing 84. 求1+2+…+n 原题链接 简单

算法

(递归) $O(n)$

C++ 代码

27 评论

AcWing 84. 求1+2+…+n 原题链接简单