echo

任生命穿梭 时间的角落

0%

求1+2+…+n

Posted on Edited on In Valine:

面试题64. 求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

对于此题我们首先想到等差数列求和公式：(1 + n) * n / 2，很可惜，我们并不能使用乘除法。我们想到使用递归来实现：

1
2
3
4
5
class Solution {
    public int sumNums(int n) {
        return n == 1 ? 1 : n + sumNums(n - 1);
    }
}

我们使用了三目运算符，也不符合题目要求，这里我们使用 && 短路与的知识，例如 A && B，当逻辑结果 A 为false 时，B 不会被执行。

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

我们还可以使用异常机制来实现递归：

1
2
3
4
5
6
7
8
9
10
class Solution {
    int[] arr = new int[]{0};
    public int sumNums(int n) {
        try{
            return arr[n];
        }catch(Exception e){
            return n + sumNums(n - 1);
        }
    }
}

时间复杂度 O(n)，空间复杂度O(n)。

我们还可以模拟乘法来解决这个问题，利用加法和移位来模拟乘法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int sumNums(int n) {
        return mul(n, n+1) >> 1;
    }

    private int mul(int a, int b){
        int ans = 0;
        for(; b != 0; b >>= 1){
            if((b & 1) == 1){
                ans += a;
            }
            a <<= 1;
        }
        return ans;
    }

}

这里我们使用了循环不符合要求，但我们注意到 n 最大为 10000，只用 14 位二进制就可表示，我们直接将循环代码写 14 次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
    public int sumNums(int n) {
        int ans = 0, a = n, b = n + 1;
        boolean flag = false;
        flag = ((b & 1) == 1) && (ans += a) > 0;
        b >>= 1;
        a <<= 1;

        flag = ((b & 1) == 1) && (ans += a) > 0;
        b >>= 1;
        a <<= 1;

        flag = ((b & 1) == 1) && (ans += a) > 0;
        b >>= 1;
        a <<= 1;

        flag = ((b & 1) == 1) && (ans += a) > 0;
        b >>= 1;
        a <<= 1;

        flag = ((b & 1) == 1) && (ans += a) > 0;
        b >>= 1;
        a <<= 1;

        flag = ((b & 1) == 1) && (ans += a) > 0;
        b >>= 1;
        a <<= 1;

        flag = ((b & 1) == 1) && (ans += a) > 0;
        b >>= 1;
        a <<= 1;

        flag = ((b & 1) == 1) && (ans += a) > 0;
        b >>= 1;
        a <<= 1;

        flag = ((b & 1) == 1) && (ans += a) > 0;
        b >>= 1;
        a <<= 1;

        flag = ((b & 1) == 1) && (ans += a) > 0;
        b >>= 1;
        a <<= 1;

        flag = ((b & 1) == 1) && (ans += a) > 0;
        b >>= 1;
        a <<= 1;

        flag = ((b & 1) == 1) && (ans += a) > 0;
        b >>= 1;
        a <<= 1;

        flag = ((b & 1) == 1) && (ans += a) > 0;
        b >>= 1;
        a <<= 1;

        flag = ((b & 1) == 1) && (ans += a) > 0;
        b >>= 1;
        a <<= 1;

        return ans >> 1;
    }
}

时间复杂度 O(log n)，空间复杂度O(1)。