找出中枢整数【LC2485】

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

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

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

• 思路

  枚举$x$，记录1 和 x 之间的所有元素之和和 x 和 n 之间所有元素之和。如果相等，那么返回$x$

  • 1 和 n 之间的所有元素之和

• 实现

  class Solution {public int pivotInteger(int n) {int right = (n + 1) * n / 2;int left = 0;for (int i = 1; i <= n; i++){left += i;if (left == right){return i;}right -= i;}return -1;}
  }
  

  • 复杂度分析

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