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

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

示例1
输入：5
返回值：15

方法一：递归求解
核心思想：
        该题目是求解等差数列的和，但是要求不使用乘除和循环语句，因此比较容易想到的方式是递归求解。

图解：

核心代码：

int Sum_Solution(int n) {
    if(n == 1)
        return n;
    return n+Sum_Solution(n-1);
}

复杂度分析：
        递归n次，因此时间复杂度为O(N)。而每次递归都需要一个额外的变量保存，因此空间复杂度为O(N)
时间复杂度O(N)
空间复杂度O(N)

方法二：采用等差计算公式
核心思想：
        该题目是求解等差数列的和，即Sn = (n+1)n/2；由于不能使用乘法，因此可以将公式进一步变形为Sn=(n*n+n)/2；而n*n可以使用自带的函数pow，即pow(n,2)，可以避免使用乘法完成。

核心代码：

int Sum_Solution(int n) {
    return ((int)pow(n, 2) + n) >> 1;
}

复杂度分析：
        直接求值发，一次执行即可，因此时间复杂度为O(1)。由于没有引入额外的数组，因此空间复杂度也为O(1)
时间复杂度O(1)
空间复杂度O(1)