面试题64_高斯求和.md

面试题 64 ：高斯求和

---

leetcode-cn 题目地址

📗difficulty： Medium

🎯Tags：

• 数学
• 递归

---

1. 题目描述📃

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

样例 1 ：

输入: n = 3
输出: 6

样例 2 ：

输入: n = 9
输出: 45

注意：

• 1 <= n <= 10000

2. 解题思路💡

以下思路来自 leetcode-cn 用户 Krahets 的题解，感谢作者的详细分析。

1+2+...+(n−1)+n 的计算方法主要有三种：平均计算、迭代、递归。

但是题目限制了一些条件，将解法引向了递归。

一种非常巧妙的办法是使用 逻辑运算符的短路效应。

逻辑运算符的短路效应

常见的逻辑运算符有三种，即 “与 && ”，“或 || ”，“非 ! ” ；而其有重要的短路效应，如下所示：

• if(A && B) // 若 A 为 false ，则 B 的判断不会执行（即短路），直接判定 A && B 为 false
• if(A || B) // 若 A 为 true ，则 B 的判断不会执行（即短路），直接判定 A || B 为 true

本题可以利用 && 实现。

代码实现

public class Solution1 {
    int res = 0;

    public int sumNums(int n) {
        boolean x = n > 1 && sumNums(n - 1) > 0;
        res += n;
        return res;
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println(new Solution1().sumNums(n));
    }
}

复杂度分析

• 时间复杂度： O(n) 。开启 n 个递归函数。
• 空间复杂度： O(n) 。递归深度为 n 。

3. 总结🎯