Easy

题目描述

给你一个正整数 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

解题思路

这道题要求找到一个中心整数 x，使得从 1 到 x 的和等于从 x 到 n 的和。

方法一：暴力枚举 对于每个可能的 x（从 1 到 n），计算左边和右边的和，检查是否相等。左边和为 1 + 2 + ... + x = x * (x + 1) / 2，右边和为 x + (x+1) + ... + n = (x + n) * (n - x + 1) / 2。

方法二：数学优化（推荐） 设左边和为 left_sum = x * (x + 1) / 2，右边和为 right_sum = (x + n) * (n - x + 1) / 2。 当 left_sum = right_sum 时，化简得到：x * (x + 1) = (x + n) * (n - x + 1) 进一步化简：x² + x = xn + n² - x² - xn + x + n 即：2x² = n² + n，所以 x² = n * (n + 1) / 2

因此我们只需要检查 n * (n + 1) / 2 是否为完全平方数即可。

方法三：前缀和 计算总和 total = n * (n + 1) / 2，然后遍历每个 x，维护左边和，检查 left_sum = total - left_sum + x 是否成立。

代码实现

class Solution {
public:
    int pivotInteger(int n) {
        int target = n * (n + 1) / 2;
        int x = sqrt(target);
        return x * x == target ? x : -1;
    }
};

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

public class Solution {
    public int PivotInteger(int n) {
        int target = n * (n + 1) / 2;
        int x = (int)Math.Sqrt(target);
        return x * x == target ? x : -1;
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var pivotInteger = function(n) {
    for (let x = 1; x <= n; x++) {
        let leftSum = x * (x + 1) / 2;
        let rightSum = (n * (n + 1) / 2) - (x * (x - 1) / 2);
        if (leftSum === rightSum) {
            return x;
        }
    }
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度数学解法暴力解法
时间复杂度O(1)O(n)
空间复杂度O(1)O(1)

相关题目