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 。

示例 2：

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

示例 3：

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

提示：

• 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;}
}

题解：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...n1...n1...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;}
}

法三：二分法

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

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;elser = mid - 1;}return -1;}
}

法四：数学O(1)做法

1 到 xxx 的元素和为 x(x+1)2\dfrac{x(x+1)}{2}2x(x+1)​，x 到 n 的元素和为 1 到 n 的元素和减去 1 到 x-1 的元素和，即 n(n+1)−x(x−1)2\dfrac{n(n+1)-x(x-1)}{2}2n(n+1)−x(x−1)​

两式相等，简化后即

x=n(n+1)2x = \sqrt{\dfrac{n(n+1)}{2}}x=2n(n+1)​​

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

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