LC-6245. 找出中枢整数（前缀和、二分法、数学）【周赛321】

6245. 找出中枢整数

难度简单3

给你一个正整数 n ，找出满足下述条件的 中枢整数 x ：

• 1 和 x 之间的所有元素之和等于 x 和 n 之间所有元素之和。

返回中枢整数 x 。如果不存在中枢整数，则返回 -1 。题目保证对于给定的输入，至多存在一个中枢整数。

示例 1：

输入：n = 8
输出：6
解释：6 是中枢整数，因为 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21 。
1
2
3

示例 2：

输入：n = 1
输出：1
解释：1 是中枢整数，因为 1 = 1 。
1
2
3

示例 3：

输入：n = 4
输出：-1
解释：可以证明不存在满足题目要求的整数。
1
2
3

提示：

• 1 <= n <= 1000

前缀和

class Solution {
    public int pivotInteger(int n) {
        int[] sum = new int[n+1];
        for(int i = 1; i <= n; i++){
            sum[i] = sum[i-1] + i;
        }
        for(int i = n; i > 0; i--){
            if(sum[i] == (sum[n]-sum[i-1])) return i;
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

题解：joey91

法一：暴力双层循环

class Solution {
    public int pivotInteger(int n) {
        for (int i = 1; i <= n; i++) {
            int pre = 0;
            for (int j = 1; j <= i; j++) pre += j;

            int suf = 0;
            for (int j = i; j <= n; j++) suf += j;

            if (pre == suf)
                return i;
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

法二：前缀和

先计算 $1...n$ 的总和，再单层循环

class Solution {
    public int pivotInteger(int n) {
        int sum = (1 + n) * n / 2;
        for (int i = 1, pre = 0; i <= n; i++) {
            pre += i;
            if (pre == sum - pre + i)
                return i;
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11

法三：二分法

能用平方根解决的都能用二分，反之则不一定。

class Solution {
    public int pivotInteger(int n) {
        for (int l = 1, r = n, tmp = (n + 1) * n / 2; l <= r; ) {
            int mid = ((r - l) >> 1) + l;
            int diff = mid * mid - tmp;
            if (diff == 0)
                return mid;
            else if (diff < 0)
                l = mid + 1;
            else
                r = mid - 1;
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

法四：数学O(1)做法

1 到 $x$ 的元素和为 $\frac{x(x+1)}{2}$，x 到 n 的元素和为 1 到 n 的元素和减去 1 到 x-1 的元素和，即 $\frac{n(n+1)-x(x-1)}{2}$

两式相等，简化后即

$x=\sqrt{\frac{n(n+1)}{2}}$

如果 x 不是整数则返回 -1。

class Solution:
    def pivotInteger(self, n: int) -> int:
        m = n * (n + 1) // 2
        x = int(m ** 0.5)
        return x if x * x == m else -1
1
2
3
4
5