LeetCode 剑指 Offer 64. 求1+2+…+n

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

示例 1：

输入: n = 3
输出: 6

限制：

1 <= n <= 10000

解法一：利用逻辑运算符的短路：

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

此算法时间复杂度为O（n），空间复杂度为O（n）。

解法二：利用虚函数求解：

class base;
vector<base *> arr;class base {
public:virtual int plus(int i) {return 0;}
};class derived : public base {
public:virtual int plus(int i) override {return i + arr[!!i]->plus(i - 1);}
};class Solution {
public:int sumNums(int n) {arr.push_back(new base());arr.push_back(new derived());return arr[!!n]->plus(n);}
};

此算法时间复杂度为O（n），空间复杂度为O（n）。

解法三：纯C环境下没有虚函数，可以使用函数指针代替：

vector<int (*)(int)> funcArr;int sum(int i) {return i + funcArr[!!(i - 1)](i - 1);
}int sumTerminator(int i) {return i;
}class Solution {
public:Solution() {funcArr.push_back(sumTerminator);funcArr.push_back(sum);}int sumNums(int n) {return funcArr[!!n](n);}
};

此算法时间复杂度为O（n），空间复杂度为O（n）。

解法四：利用static成员：

class Solution {
public:Solution() {sum += i;++i;}int sumNums(int n) {i = 1;sum = 0;vector<Solution *> temp;for (int i = 0; i < n; ++i) {temp.push_back(new Solution);}return sum;}static int i;static int sum;
};int Solution::i = 1;
int Solution::sum = 0;

此算法时间复杂度为O（n），空间复杂度为O（n）。

解法五：利用模板，在编译期计算出结果，但这种方式需要输入是constexpr的：

class Solution {
public:template<int N> struct ans {enum {sum = N + ans<N - 1>::sum};};template<> struct ans<1> {enum {sum = 1};};int sumNums() {return ans<5>::sum;    // 模板参数需要是constexpr的}
};

此算法时间复杂度为O（1），空间复杂度为O（1）。

解法六：将enum改为const static int，在较老的不支持类内const static的编译器上，常用enum代替const static，这种方法也需要模板参数是constexpr的：

class Solution {
public:template<int N> struct ans {const static int sum = N + ans<N-1>::sum;};template<> struct ans<1> {const static int sum = 1;};int sumNums() {return ans<3>::sum;}
};

此算法时间复杂度为O（1），空间复杂度为O（1）。

解法七：利用数组大小，根据求和公式sum = i(i+1)/2：

class Solution {
public:int sumNums(int i) {bool arr[i][i+1];return sizeof(arr) >> 1;}
};

此算法时间复杂度为O（n），空间复杂度为O（n）。

解法八：对于相乘的两个数A和B，将B转换为二进制，如果B中的第i位为1，这位1对结果的贡献为A * (1 << i)，这个方法也被称作俄罗斯农民乘法，经常被用于两数相乘取模的场景，如果两数相乘已经超过数据范围，但取模后不会超过，我们就可以利用这个方法来拆位取模计算贡献，保证每次运算都在数据范围内。将其应用到求和公式：

class Solution {
public:int sumNums(int i) {int a = i, b = i + 1;int ans = 0;while (b) {if (b & 1) {ans += a;}b >>= 1;a <<= 1;}return ans >> 1;}
};

但是题目要求不能使用while循环，由于题目要求中对输入有限制，n最大为10000，因此最多循环14次，我们把循环中内容写14次即可：

class Solution {
public:int sumNums(int i) {int a = i, b = i + 1;int ans = 0;(b & 1) && (ans += a);b >>= 1;a <<= 1;(b & 1) && (ans += a);b >>= 1;a <<= 1;(b & 1) && (ans += a);b >>= 1;a <<= 1;(b & 1) && (ans += a);b >>= 1;a <<= 1;(b & 1) && (ans += a);b >>= 1;a <<= 1;(b & 1) && (ans += a);b >>= 1;a <<= 1;(b & 1) && (ans += a);b >>= 1;a <<= 1;(b & 1) && (ans += a);b >>= 1;a <<= 1;(b & 1) && (ans += a);b >>= 1;a <<= 1;(b & 1) && (ans += a);b >>= 1;a <<= 1;(b & 1) && (ans += a);b >>= 1;a <<= 1;(b & 1) && (ans += a);b >>= 1;a <<= 1;(b & 1) && (ans += a);b >>= 1;a <<= 1;(b & 1) && (ans += a);b >>= 1;a <<= 1;return ans >> 1;}
};

此算法时间复杂度为O（lgn），空间复杂度为O（1）。