求1-n的和


题目描述

求 1+2+…+n ,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。

示例 1:

输入: n = 3
输出: 6

示例 2:

输入: n = 9
输出: 45

限制:

1 <= n <= 10000

递归

由于题目限制了很多,其中比较常用的for循环方法也被禁用,那么不用for循环,最容易想到的就是递归,于是我们很容易就能写出递归的版本

1
2
3
public int sumNums(int n) {
return n == 0 ? 0 : n + sumNums(n - 1);
}

但是题目要求不允许使用条件判断语句,那么我们是否能使用别的办法来确定递归出口呢?答案就是逻辑运算符的短路性质。以逻辑运算符 && 为例,对于 A && B 这个表达式,如果 A 表达式返回 false ,那么 A && B 已经确定为 false ,此时不会去执行表达式 B。同理,对于逻辑运算符 ||, 对于 A || B 这个表达式,如果 A 表达式返回 true ,那么 A || B 已经确定为 true ,此时不会去执行表达式 B。

利用这一特性,我们可以将判断是否为递归的出口看作 A && B 表达式中的 A 部分,递归的主体函数看作 B 部分。如果不是递归出口,则返回 true,并继续执行表达式 B 的部分,否则递归结束。当然,你也可以用逻辑运算符 || 给出类似的实现,这里我们只提供结合逻辑运算符 && 的递归实现。

1
2
3
4
public int sumNums(int n) {
boolean flag = n > 0 && (n += sumNums(n - 1)) > 0;
return n;
}

复杂度分析

  • 时间复杂度:O(n),递归函数递归 n 次,每次递归中计算时间复杂度为 O(1),因此总时间复杂度为 O(n)。
  • 空间复杂度:Ο(n),递归函数的空间复杂度取决于递归调用栈的深度,这里递归函数调用栈深度为 O(n),因此空间复杂度为 O(n)。

Java流API

其实这种数学计算,包含求和,求大小等等操作,Java引入很多方便的方法,此题使用了Java流API IntStream.range(1, n + 1).sum(),求指定范围的整数和。关于流API的介绍可以参考:

Java 8 的 Lambda 表达式和 Stream API

1
2
3
public int sumNums2(int n) {
return IntStream.range(1, n + 1).sum();
}

来源

求1-n的和 | 力扣(LeetCode)
求1-n的和 | 题解(LeetCode)


文章标题:求1-n的和
文章作者:cylong
文章链接:http://www.cylong.com/blog/2020/06/03/qiu-12n-lcof/
有问题或者建议欢迎在下方评论。欢迎转载、引用,但希望标明出处,感激不尽(●’◡’●)