求1+2+…+n

题目描述

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

示例 1：

1 2	输入: n = 3 输出: 6

示例 2：

1 2	输入: n = 9 输出: 45

限制：
1 <= n <= 10000

题目链接

Leetcode

题目解答

解法一

不考虑题目限制的话，我们可以借助求和公式直接计算出结果。

时间复杂度:$O(1)$ 空间复杂度:$O(1)$

class Solution {
    public int sumNums(int n) {
        return n * (n + 1) >> 1;
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：35.2 MB, 在所有 Java 提交中击败了91.68%的用户

解法二

A:False B:True
A && B = False // 短路

A:True B:False
A && B = False // 非短路

考虑题目给出的限制条件，我们可以通过递归的方式累加求和，但是需要考虑递归终止条件，由于限制使用if和条件判断语句（A?B:C），只能采取其他方式。定义A、B两个表达式，进行逻辑运算A && B，如果A表达式不满足条件，B表达式就不会被执行，这就是逻辑运算的短路性质，利用这个性质我们把B表达式作为递归入口，当A表达式不成立的时候，递归终止。

时间复杂度:$O(n)$ 空间复杂度:$O(n)$

class Solution {
    public static int sumNums(int n) {
        boolean stop = (n > 1) && (n += sumNums(n - 1)) > 0;
        return n;
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：35.6 MB, 在所有 Java 提交中击败了65.01%的用户