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

本文主要是介绍剑指Offer 64. 求1 + 2 + ... + n，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

输入：5
返回值：15

方法一：不使用if的递归
求解 1 + 2 + ⋯ + n 1+2+\cdots+n 1+2+⋯+n，有以下几种方法：(1)使用高斯公式 s u m = n ( 1 + n ) / 2 sum=n(1+n)/2 sum=n(1+n)/2，但是题目中明确限制使用乘除法，所以此方法不可行。(2)使用循环求解，但是题目中又限制使用for、while，所以此方法也不可行。(3)递归方法，代码如下：

public int sum(int n) {
    if (n == 1) return 1;
    return n + sum(n - 1);
}

但是此方法中使用了if语句，所以表面上看，递归方法也是不行。进一步考虑，if是用于递归结束，如果n == 1，递归结束，如果n > 1，继续递归，这可以通过短路与&&来实现，即(n > 1) && ((n + sum (n - 1)) > 0)，因为n == 1时，第一个判断为false，短路与就不进行第一个判断，递归结束；当n > 1时，第一个判断为true，短路与还需要进行第二个判断，即继续递归，和上面的代码逻辑一致。

public class Solution {
    public int Sum_Solution(int n) {
        boolean b = (n > 1) && ((n += Sum_Solution(n - 1)) > 0);
        return n;
    }
}

时间复杂度：依次需要计算每一个整数的和， O ( n ) O(n) O(n)；空间复杂度：每次计算都需要开辟栈， O ( n ) O(n) O(n)。

结束语：如果本篇博客对您有帮助，请点赞、收藏或关注，您的鼓励是博主进步的动力，感谢支持，共同进步。

这篇关于剑指Offer 64. 求1 + 2 + ... + n的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！