题目链接：https://leetcode.cn/problems/qiu-12n-lcof/

1. 题目介绍（64. 求1+2+…+n）

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

【测试用例】：

【条件约束】：

2. 题解

2.1 逻辑运算符短路 – O(n) ⭐

时间复杂度 O(n)，空间复杂度 O(n)

【解题思路】：
关于求 1+ 2 + 3 + … + n的解法有很多，如：

1. 平均计算：公式法：（n*(n+1)）/2
   
   问题： 此计算必须使用 乘除法 ，因此本方法不可取，直接排除
2. 迭代：循环计算
   
   问题： 循环必须使用 while 或 for，因此本方法不可取，直接排除
3. 递归：同迭代类似，可以不需要 while 或 for之类的循环关键字，但必须设置一个递归终止条件，否则就会无限递归下去
   
   问题： 终止条件需要使用 if ，因此本方法不可取。
   思考： 除了 if 和 switch 等判断语句外，是否有其他方法可用来终止递归？

……
【实现策略】：
……
以上三种解题思路就是我们在解决 1+2+…+n 上的常见思路，但均会涉及到题目禁用的关键字，那么如何不使用这些关键字，还能解决本题呢？
……
逻辑运算符短路：常见的逻辑运算符有三种，即 “与 && ”，“或 ∣∣ ”，“非 ! ” ；而其有重要的短路效应，短路效果如图所示：

通过逻辑运算符的短路效应，我们就可以让其替代 if 实现递归终止条件的判断：

class Solution {
    // Soluition1：逻辑运算符短路
    // A && B, 当 A 满足条件时， B才会被执行
    // A || B, 与 && 相反，当 A 满足条件时，B 就不会再被执行
    public int sumNums(int n) {
        // n + n-1 + n-2 + …… + 1
        boolean x = n > 1 && (n += sumNums(n - 1)) > 0;
        return n;
    }
}

2.2 快速乘（俄罗斯农民乘法）– O(logn)

时间复杂度O(logn)，空间复杂度O(1)

【解题思路】：
手动展开循环，是个狠人！
关于俄罗斯农民乘法相关内容可参考：俄罗斯农民乘法

class Solution {
    public int sumNums(int n) {
        int ans = 0, A = n, B = n + 1;
        boolean flag;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A  1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A  1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A  1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A  1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A  1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A  1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A  1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A  1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A  1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A  1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A  1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A  1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A  1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A  1;
        B >>= 1;

        return ans >> 1;
    }
}

2.3 JDK IntStream – O(n)

时间复杂度 O(n)，空间复杂度 O(n)

【解题思路】：
Java8支持的流处理的元素类型只有4种，double、int，long和reference类型，该题没限制用库函数，算是投机取巧了。
关于 IntStream 的相关内容可参考：Java8 Stream API 之 IntStream 用法全解

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

3. 参考资料

[1] 面试题64. 求 1 + 2 + … + n（逻辑符短路，清晰图解）– Krahets
[2] 求1+2+…+n – 力扣官方题解

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net