剑指offer 47. 求1 + 2 + 3 + .... + n

47. 求1 + 2 + 3 + .... + n

题目描述

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

思路一：

使用 && 运算符实现 if(n != 0)条件判断，因为 Java 的双与运算符左右两边都必须是 boolean 类型，所以右边加一个 “== 0”, 并且 Java 的表达式不能单独存在，所以把 && 的结果返回给一个变量

1 public class Solution {
2     public int Sum_Solution(int n) {
3         int sum = n;
4         boolean flag = ((n != 0) && (sum += Sum_Solution(n - 1)) == 0);
5         return sum;
6     }
7 }

复杂度分析

空间复杂度：取决于栈的深度，为O(n)

时间复杂度：O(n)

思路二：

利用求和公式和 pow() 函数

1 + 2 + ... + n = n * (n + 1) / 2 = (n^2 + n) / 2

所以 1 + 2 + ... + n = ( pow(n, 2) + n) / 2;

1 class Solution {
2     public int sumNums(int n) {
3         
4         // n*(n+1)/2 ==> (n^2 + n)/2, 除运算用右移运算符代替
5         int temp = (int)Math.pow(n, 2) + n;
6         return temp >> 1;
7     }
8 }

复杂度分析：

空间复杂度和时间复杂度都O(1), 但是这个写法其实有点违规，因为pow函数其实内部用到了乘法运算