题目链接：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的解法有很多，如：
- 平均计算：公式法：
（n*(n+1)）/2
问题： 此计算必须使用 乘除法 ，因此本方法不可取，直接排除- 迭代：循环计算
问题： 循环必须使用 while 或 for，因此本方法不可取，直接排除- 递归：同迭代类似，可以不需要 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();
}
}
文章来源：https://www.toymoban.com/news/detail-421798.html
3. 参考资料
[1] 面试题64. 求 1 + 2 + … + n（逻辑符短路，清晰图解）-- Krahets
[2] 求1+2+…+n – 力扣官方题解文章来源地址https://www.toymoban.com/news/detail-421798.html
到了这里，关于【LeetCode】剑指 Offer 64. 求1+2+…+n p307 -- Java Version的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
