求1+2+3+...+n_牛客博客

题目的主要信息：

计算 $1 + 2 + 3 + . . . + n$
不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）

举一反三：

学习完本题的思路你可以解决如下题目：

JZ65. 不用加减乘除做加法

JZ15. 二进制中1的个数

JZ56. 数组中只出现一次的两个数字

方法：与运算的短路递归（推荐使用）

知识点：位运算

计算机的数字由二进制表示，我们平常的运算是对整个数字进行运算，但是还可以按照二进制的每一位分别进行运算。常见运算有位与、位或、移位、位异或等。

具体做法：

从1连加到n，不能使用城乘除法，那就只能相加了。一个一个加，但是循环需要判断什么时候截止，我们又不能用关键词，这就难办了。

如果我们的和加上了 $n$ ，则剩余的问题就是该数字加上1到 $n - 1$ 的和，这是一个子问题，因此可以用递归，从 $n$ 回到1，再累加递归的结果。但是我们需要判断递归停止的条件，即到0时停止递归，不能用if、switch、？：等操作，我们可以采用与运算的短路操作： 在函数中，如果与运算成立，则继续，否则终止函数直接返回false。

具体做法：

step 1：用与运算判断n是否为正数，如果不是则结束递归。
step 2：如果是累加子问题的和，并返回n。

图示：

alt

Java实现代码：

public class Solution {
    public int Sum_Solution(int n) {
        //通过与运算判断n是否为正数，以结束递归
        boolean flag = (n > 1) && ((n += Sum_Solution(n - 1)) > 0); 
        return n;
    }
}

C++实现代码：

class Solution {
public:
    int Sum_Solution(int n) {
        //通过与运算判断n是否为正数，以结束递归
        n && (n += Sum_Solution(n - 1)); 
        return n;
    }
};

Python实现代码：

class Solution:
    def __init__(self):
        self.res = 0
    def Sum_Solution(self , n: int) -> int:
        #通过与运算判断n是否为正数，以结束递归
        n > 1 and self.Sum_Solution(n - 1)
        self.res += n
        return self.res

复杂度分析：

时间复杂度： $O (n)$ ，一共递归 $n$ 次
空间复杂度： $O (n)$ ，递归栈深度为 $n$