题目

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

示例 1：

输入: n = 3
输出: 6

示例 2：

输入: n = 9
输出: 45

限制：

  • 1 <= n <= 10000

解答

  1. 错误解法（使用了if）,虽然通过了但是不符合题意。
class Solution {
public:
    int sumNums(int n) {
        if(n == 1)
        {
            return 1;
        }
        else
        {
            return n + sumNums(n - 1);
        }
    }
};
  1. 由于不能使用乘除法，for，while等关键字以及条件判断语句，因此我们能用的挚友加减法，赋值，位运算符和逻辑运算符。

但是如果使用递归方法，那么递归的结束条件很难不用条件判断语句，那么怎么解决？答案是使用逻辑运算符&&或者||，利用它的短路性质，对于 A && B 这个表达式，如果 A 表达式返回 False ，那么 A && B 已经确定为 False，此时不会去执行表达式 B。同理，对于逻辑运算符 ||， 对于 A || B 这个表达式，如果 A 表达式返回 True ，那么 A || B 已经确定为 True ，此时不会去执行表达式 B。

因此我们可以将判断是否为递归的出口看作A&B表达式中的A部分，递归的主体函数看作B部分。如果不是递归出口，就返回True，并继续执行表达式B的部分，否则递归结束。结合逻辑运算符&&的递归实现如下：

class Solution {
public:
    int sumNums(int n) {
        n && (n += sumNums(n-1));
        return n;
    }
};

用逻辑运算符||的递归实现如下：

class Solution {
public:
    int sumNums(int n) {
        n==1 || (n += sumNums(n-1));
        return n;
    }
};
  1. 使用C++的sizeof函数进行$\frac{1}{2}(n \times (n+1))$的模拟：
class Solution {
public:
    int sumNums(int n) {
        bool a[n][n+1]; //bool一个元素占一bit
        return sizeof(a) >> 1; //sizeof(a) 计算了n*(n+1)
    }
};