2485. 找出中枢整数

LC每日一题，参考2485. 找出中枢整数。

题目

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

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

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

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

解题思路

• 枚举：利用等差数列求和公式，用整个数列和与枚举到某个下标时计算的和进行对比。
• 二分查找：本质是查找，适用二分查找，根据数列和公式转化查找条件。

枚举

class Solution {
    public int pivotInteger(int n) {
        //等差数列求和
        int ans = 0;
        for(int i = 1,sum = 0; i <= n; i++) {
            sum += i;
            if(sum*2 == n*(n+1)/2+i) return i;
            else if(sum*2 > n*(n+1)/2+i) break;
        }
        return -1;
    }
}

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

二分查找

class Solution {
    public int pivotInteger(int n) {
        //化简+二分 i*(i+1)/2*2 == n*(n+1)/2+i -> i*i = n*(n+1)/2
        int res = n*(n+1)/2,left = 1,right = n;
        while(left <= right) { //也可直接使用api函数(int) Math.sqrt(res)
            int mid = (left+right)>>1;
            if(mid*mid == res) return mid;
            else if(mid*mid > res) right = mid-1;
            else left = mid+1;
        }
        return -1;
    }
}

复杂度分析

• 时间复杂度：O(logn)。
• 空间复杂度：O(1)。