LeetCode.剑指offer.064.计算1到n的和

题目描述

《剑指offer》面试题64. 求1+2+…+n
https://leetcode-cn.com/problems/qiu-12n-lcof/

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

示例 1：

输入: n = 3
输出: 6

示例 2：

输入: n = 9
输出: 45

限制：1 <= n <= 10000

---

相似题目

LeetCode.剑指offer.064.计算1到n的和

LeetCode.371.Sum of Two Integers 不用加减号计算整数加法

LeetCode.069.Sqrt(x) x的平方根
LeetCode.050.Pow(x,n) 实现Pow(x,n)

---

解题过程

利用逻辑运算的短路特性

对于逻辑运算符 ||， 对于 A || B 这个表达式，如果 A 表达式返回 true ，那么 A || B 已经确定为 true ，此时不会去执行表达式 B。

时间复杂度 O(n)，空间复杂度 O(n)（递归栈深度）

private static class SolutionV202006 {
    public int sumNums(int n) {
        boolean temp = (n == 0 || (n += sumNums(n - 1)) >= 0);
        return n;
    }
}

快速乘

---

GitHub代码

algorithms/leetcode/offer/_064_1ToNSum.java
https://github.com/masikkk/algorithms/blob/master/leetcode/offer/_064_1ToNSum.java

---