AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

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

作者: 作者的头像   cornerCao ,  2019-01-17 15:18:50 ,  所有人可见 ,  阅读 10574


118


66

算法

(递归) $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      7    踩      回复

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

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

用户头像
FITINGQG   2022-11-26 15:14      1    踩      回复

orz


用户头像
志秋世   2021-12-23 17:11      1    踩      回复

短路好评


用户头像
acwing_3914   2024-09-13 15:17         踩      回复

666


用户头像
lsxstart   2024-07-01 14:36         踩      回复

有想法,牛逼


用户头像
doilion   2024-03-10 00:39         踩      回复

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         踩      回复

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

用户头像
Kingna   2022-08-12 22:04         踩      回复

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

用户头像
种花家的老六   2022-08-13 10:27    回复了 Kingna 的评论      1    踩      回复

哦


用户头像
北冥有好多鱼   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 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息