【每日算法Day 2】限制运算方式求1到n的和：学到了快速乘法
# 题目链接
LeetCode 64. 求1+2+…+n (opens new window)
# 题目描述
求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。保证1 <= n <= 10000。
# 示例
输入:
n = 3
输出:
6
2
3
4
# 解题思路
# 1. 使用递归+短路/异常机制
由于不能使用for/while循环做加法，看到这题我个人的思路是使用递归来代替循环，那么就能写出如下代码：
public int sumNums(int n) {
if(n>1)
return n+sumNums(n-1);
else
return n;
}
2
3
4
5
6
然而题目又限制不能使用if、switch和三目运算（A?B:C）来直接作判断并执行动作，则可以钻个空子使用短路来实现判断与执行动作：
public int sumNums(int n) {
boolean b = n>=1 && ((n+=sumNums(n-1))>0);
return n;
}
2
3
4
使用递归的时间复杂度为O(n)。递归函数递归 n 次，每次递归中计算时间复杂度为O(1)，因此总时间复杂度为O(n)；空间复杂度为O(n)，这里递归函数调用栈深度为O(n)，因此空间复杂度为O(n)。
甚至可以使用异常机制来实现不作判断直接尝试执行加法动作（会慢一些）：
class Solution {
int[] test=new int[]{0};
public int sumNums(int n) {
try{
return test[n];
}catch(Exception e){
return n+sumNums(n-1);
}
}
}
2
3
4
5
6
7
8
9
10
# 2. 快速乘（官方解法2）
这一题如果不加任何限制那么大家最先想到的应该不是迭代/递归而是使用等差数列求和公式n(n+1)/2。不能使用乘除则可以尝试用位运算对该式求解，其中除2可以用右移1位代替，关键在于求两个正整数的乘积。而求乘积则可以用俄罗斯农民乘法转换为位移运算和加法运算（系统地将n除以2，同时将m乘以2,n为奇数时将当前的m附加到结果中）。
示例：50*65
n m 附加值
50 65
25 130
12 260 130
6 520
3 1040
1 2080 1040
则最终结果为2080+1040+130
2
3
4
5
6
7
8
9
10
一般情况下，写出一个循环执行该过程，循环的终止条件是n==0。但是由于限制了不可以使用循环，则可以手动展开该循环，并使用短路来控制，题目给出的n<=10000，则该过程最多执行14次。
# 个人原创方法(伪)
官方第二种题解给出的手动展开的方法还是挺丧心病狂的，如果n较大的话就需要写很多次（即使题目为了避免乘积溢出限制n<=10000手动写14次也是很多的。如果条件改为使用long并且n<=10^9岂不是要手动展开26次？）。而循环在很多情况下也可以用递归等价替换，使用快速乘的方法和递归并不冲突。
在我个人看来，为了避免使用for/while关键字可选择手动展开循环或者递归，为了根据条件执行相应的计算动作同时避免使用if或三目运算符?可使用短路（或有位老哥想到利用异常不加判断都尝试执行一遍），而执行计算本身可以选择单纯的加法或由等差数列求和公式到俄罗斯农民乘法将乘法转换为多次移位和加法。
所以解题的方法理论上可以从{手动循环,递归}+{短路逻辑运算符,异常（不推荐）}+{直接相加,求和公式结合俄罗斯农民乘法}这三个集合的笛卡尔积中任选一个。下面给出使用快速乘+递归+短路逻辑运算符的方法。
public int sumNums(int n) {
//等差数列求和公式n(n+1)/2
return multiply(n,n+1)>>1;
}
private int multiply(int n, int m){
boolean b=(n>1)&&(((n&1)==1&&(m=m+multiply(n>>1,m<<1))>0)||((n&1)==0)&&(m=multiply(n>>1,m<<1))>0);
return m;
}
2
3
4
5
6
7
8
9
multiply()方法使用了快速乘但很简洁，也许你会说可读性不佳，但仔细看&&运算符仅仅是用来控制选择计算动作的，判断逻辑和下面使用if条件判断的代码效果一致。
private int multiply(int n, int m){
if(n>1){
if(n%2==1){
m=m+multiply(n/2,m*2);
}else{
m=multiply(n/2,m*2);
}
}
return m;
}
2
3
4
5
6
7
8
9
10
其实应该也算不上原创，众所周知迭代和递归往往能相互转换，只是似乎没看到有这样的题解，就吹嘘一波2333。