找出中枢整数

难度:

标签:

题目描述

Given a positive integer n, find the pivot integer x such that:

The sum of all elements between 1 and x inclusively equals the sum of all elements between x and n inclusively.

Return the pivot integer x. If no such integer exists, return -1. It is guaranteed that there will be at most one pivot index for the given input.

Example 1:

Input: n = 8
Output: 6
Explanation: 6 is the pivot integer since: 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21.

Example 2:

Input: n = 1
Output: 1
Explanation: 1 is the pivot integer since: 1 = 1.

Example 3:

Input: n = 4
Output: -1
Explanation: It can be proved that no such integer exist.

Constraints:

1 <= n <= 1000

代码结果

运行时间: 26 ms, 内存: 16.0 MB

// Java Stream Solution
// 思路：
// 1. 计算1到n之间所有整数的总和totalSum。
// 2. 使用Java Stream遍历1到n之间的整数，计算左侧和右侧的和，检查是否存在中枢整数。

import java.util.stream.IntStream;

public class PivotIntegerStream {
    public int findPivot(int n) {
        int totalSum = IntStream.rangeClosed(1, n).sum();
        return IntStream.rangeClosed(1, n)
                .filter(x -> IntStream.rangeClosed(1, x).sum() == totalSum - IntStream.rangeClosed(1, x).sum())
                .findFirst()
                .orElse(-1);
    }
}

解释

方法:

该题解的整体思路是通过迭代找出中枢整数x。首先，计算从1到n的总和total。然后，通过一个循环逐步计算从1到当前值value的累加和current，同时从total中减去当前的value，以此模拟两侧的和。如果在某一点，current等于total，那么这一点就是中枢整数x。如果循环结束后没有找到这样的点，返回-1。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆

如何确定题目中的'中枢整数'定义是否需要包含该整数本身在内的累加和？

▷

题目中的中枢整数的定义包含该整数本身在内的累加和。这是因为题目要求从1到x的所有整数之和等于从x到n的所有整数之和。因此，x本身被包含在从1到x的累加和中，并且也是计算从x到n的累加和的起始点。

🦆

在计算total时，直接使用了(1 + n) * n / 2的公式，这个公式是如何得来的，它代表什么意义？

▷

公式(1 + n) * n / 2是等差数列求和的公式。这个公式用于计算从1到n的所有整数的和。在这个公式中，1是首项，n是末项，n是项数。该公式的意义在于快速计算连续整数的总和，无需逐一加总每个数，提高了计算效率。

🦆

在循环中，current和total都在同步更新，有没有可能出现在不同的value值时，current等于total的情况？

▷

在循环中，虽然current和total都在同步更新，但设计的逻辑确保只有在某一个特定的value值时current才可能等于total。这是因为每次循环都会先将current增加当前的value，然后比较current和total，之后才将value从total中减掉。因此，只有在current累加到某一点恰好等于原始total减去之前所有value的一半时，current才会等于total。如果没有这样的点，循环结束后返回-1。

找出中枢整数

题目描述

代码结果

解释

代码细节讲解

相关问题