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

作者：

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

93

53

算法

(递归) $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;
    }
};

24 评论

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

短路好评

卯花之佐久夜姬 21天前

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

晓月兮清风 1个月前

酱紫不行吗

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

就你也想和老爹过过手吗 1个月前

不能用if

达不溜达 4个月前

用短路运算太帅了

15082154025 8个月前

amz

般若巴麻空 10个月前

tql

mkkk123fromage 10个月前

orz

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

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

stOtue 2022-08-12 22:04

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

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

哦

北冥有好多鱼 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

bala 2020-03-18 16:51

tql

_empty 2019-05-12 20:17

我本来也想递归的但是不会短路所以自闭了

Clever_Jimmy 2019-07-10 16:50

主要就是想不到短路……qwq