AcWing-84. 求1+2+…+n

84. 求1+2+…+n

比较需要思考的题目,如果仅是不能使用乘除,还可以使用位运算来弥补,对于加减则比较麻烦。这里自己只能想到最笨的方法??,而且AcWing还增强了数据，仅仅是int型过不了。

class Solution {
public:
    int getSum(int n) {
        long long ans = 1;
        ans = ans * n * (1 + n);
        ans /= 2;
        return ans;
    }
};

看到评论区有一位大佬的思路很巧妙，说是取巧却也合理。考虑到char数据类型的所占用的空间为1字节，定义一个二维数组，每一维大小分别为\(n\)和\(n+1\)。对其使用sizeof运算符求得其大小后再右移1位，即除以2。??

class Solution {
public:
    int getSum(int n) {
        char a[n][n + 1];
        return sizeof a >> 1;
    }
};

上述代码不可谓不巧，还有一种比较多人用的方式是尾递归法，将结果作为参数一直传递下去。
根据递推公式得：sum(n) = n+sum(n - 1)，由于不能够使用if流程控制，考虑使用&&短路与运算将其截断退出。
寻常递归将如下所示：

class Solution {
public:
    int getSum(int n) {
        if(n == 0) return 0;
        else return n + getSum(n - 1);
    }
};

而使用&&运算符将其做短路运算则为如下所示：

class Solution {
public:
    int getSum(int n) {
        int res = n;
        (n>0) && (res += getSum(n-1));//利用短路运算终止递归
        return res;
    }
};