LeetCode - 64.求1+2+...+n

发表于 2021-06-21 分类于 LeetCode 阅读次数： Valine：

题面

求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
样例
1
2
输入: n = 3
输出: 6
1
2
输入: n = 9
输出: 45

思路

可以先思考通过求和公式 n * (n + 1) >> 1 但这种方式必须要用乘法，不然的话需要if来做判断，在偶数那里 >> 1 ，所以这个思路会行不通。

通过循环来求和 while(n) sum += (n--); 但是会用到while可这已经很精简了，没有用到乘除法只是多了一个while，while又可以通过递归消掉。

思考如何去掉while循环，这里要明确一点，在 C/C++ 中&&和||操作并不是对两个操作数都去判断一下，而是当&&, ||第一个操作数就已经满足条件的情况下不会再去判断第二个操作数了，利用这一点可以作为递归的边界判断。
假设当前循环到了 $x$
- !x || (sum += x) 表示当 $x$ 达到向下循环边界 0 时返回 false，这时递归停止
- x && （sum += x) 表示当 $x$ 达到向下循环边界 0 时返回 false，递归停止
- x ^ n 表示当 $x$ 达到向上循环边界 n 时递归停止，但是这种方法需要另一个函数的配合

代码

3种

int sumNums(int n) {
    !n || (n += sumNums(n - 1));
    return n;
}

int sumNums(int n) {
    n && (n += sumNums(n - 1));
    return n;
}

int subSum(int x, int n) {
    (x ^ n) && (x += subSum(x + 1, n));
    return x;
}
int sumNums(int n) {
    return subSum(1, n);
}