剑指Offer（四十七)-求1+2+3+…+n(Java版)

描述

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

数据范围： 0 < n le 2000

进阶： 空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n)

示例1

输入：5

返回值：15

示例2

输入：1

返回值：1

 上述问题明显是一个等差数列求和问题，等差数列求和公式 sn = (a1 + an）*n /2 ,其中an =  n,a1 =1; 所以结果为sn = (1 + n) *n /2 = (n + n*n) /2; n*n我们可以借用math.pow函数来实现，而除于2 则可以右移一位来解决。所以代码如下

 public int firstSum_Solution(int n) {
        int sum = (int)Math.pow(n,n) + n;
        return sum >> 1;
    }

使用递归来实现，难点在于如何停止递归，我们借助&&来进行判断实现，代码如下

public int secondSum_Solution(int n) {
        int sum = n;
        boolean flag =  (n > 0) && ((sum+=secondSum_Solution(n-1))>0);
        return sum;
    }

就是利用java的异常机制来解决问题，代码如下

public int thirdSum_Solution(int n) {
        try {
            int i = 1 /n;
            n += thirdSum_Solution(n-1);
        }catch (Exception e){

        }
        return n;
    }