题解 | #求1+2+3+...+n#

题目：求1+2+3+...+n

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

递归思路分析：首先判断当n的值为0时，可以直接返回最后的结果值为0。当n的值大于0时，使用递归算法来计算最终的结果。利用逻辑与关系判别实现递归是否终止。

实例分析：输入：5

具体C++代码如下所示： 

class Solution {
public:
    int Sum_Solution(int n) {
        if(n <= 1) 
            return n; 
        int res = n; 
        res && ( res = res + Sum_Solution(n-1) ); 
        return res; 
    } 
};

时间复杂度：O(N)，空间复杂度：O(N)。

        

具体C++代码如下所示： 

class Solution {
public:
    int Sum_Solution(int n) {
        int sum = 0;
        sum = n*(n + 1)/2;
        return sum;
    }
};

时间复杂度为O(1)，空间复杂度为O(1)。

public class Solution {
    public int Sum_Solution(int n) {
        int sum=(int)Math.pow(n, 2)+n;//Math.pow(a,b)表示a^b
        return sum>>1;//右移一位相当于除以2。
    }
};