求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循环，最容易想到的就是递归，于是我们很容易就能写出递归的版本

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 的部分，否则递归结束。当然，你也可以用逻辑运算符 || 给出类似的实现，这里我们只提供结合逻辑运算符 && 的递归实现。

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的介绍可以参考：

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

文章标题：求1-n的和 文章作者：cylong 文章链接：https://0skyu.cn/p/3571.html 有问题或者建议欢迎在下方评论。欢迎转载、引用，但希望标明出处，感激不尽(●’◡’●)