求1+2+…+n的特殊算法

剑指Offer的题目，有点意思

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

示例 1：

输入: n = 3
输出: 6

示例 2：

输入: n = 9
输出: 45

限制：

• 1 <= n <= 10000

算法1：

对于Java，可以使用Stream，一句话搞定：

class Solution {
    public int sumNums(int n) {
        return IntStream.rangeClosed(1,n).sum();
    }
}

IntStream.rangeClosed(1,n)产生一个1，2，3直到n的整数流，sum()方法直接求和。

算法2：

对于C这样的比较低级的高级语言，可以用递归来实现。

Java递归的算法：

class Solution {
    
    private int result = 0;
    public int sumNums(int n) {
        boolean flag = n>1 && sumNums(n-1) > 0;
        result += n;
        return result;
    }
}

递归的方法不好理解，要点：

当n>1成立时会执行sumNums(n-1) > 0；

当n>1不成立就不会执行sumNums(n-1) > 0，从而不使用if也能终止递归过程。

算法3：利用Arrays.setAll()函数

在填充数组的同时，把数组的下标号累加，从而实现求和。

Java代码如下：

class Solution {
    
    private static int sum = 0;

    public int sumNums(int n) {
        sum = 0;
        int[] array = new int[n+1];  //准备数组
        Arrays.setAll(array, ind -> {
            sum += ind;  //累加索引号
            return ind;
        });
        return sum;
    }
}

算法4：利用Math.pow()和位运算

总和 = n * (n+1) /2 = (n*n + n) / 2

可以利用Math.pow()求平方；

利用位运算做除法；

利用(int)把浮点数变成整数；

Java代码如下。这个运算速度最快！

class Solution {
    
    public int sumNums(int n) {
        return (int) (Math.pow(n, 2) + n + 0.5) >> 1;
    }
}