leetcode
leetcode 1901 ~ 1950
拆分成最多数目的正偶数之和

拆分成最多数目的正偶数之和

难度:

标签:

题目描述

代码结果

运行时间: 358 ms, 内存: 25.8 MB


// 题目思路:
// 我们需要将 finalSum 分解为多个互不相同的正偶数之和,且要使这些正偶数的数目最多。
// 为了达到这个目标,我们可以从最小的正偶数 2 开始,然后不断加上下一个偶数,直到无法再继续。
// 如果 finalSum 剩余的部分不能再分解出一个新的正偶数,则将当前结果返回。

import java.util.stream.LongStream;
import java.util.stream.IntStream;

public class Solution {
    public int[] maximumEvenSplit(long finalSum) {
        // 如果 finalSum 不是偶数,直接返回空数组
        if (finalSum % 2 != 0) return new int[0];
        // 使用 Stream 生成偶数流
        long[] result = LongStream.iterate(2, n -> n + 2)
                                  .takeWhile(n -> finalSum >= n)
                                  .toArray();
        long sum = LongStream.of(result).sum();
        // 如果还有剩余,说明我们少加了一个数,把剩余的数加到最后一个数上
        if (sum < finalSum) {
            result[result.length - 1] += (finalSum - sum);
        }
        // 转换结果为 int 数组
        return IntStream.of(result).mapToInt(Long::intValue).toArray();
    }
}

解释

方法:

首先检查`finalSum`是否为偶数,因为只有偶数才能被拆分为若干个互不相同的正偶数之和。如果是奇数,则直接返回空数组。接着,将`finalSum`除以2,以简化计算,因为我们关心的是将其分解为连续的正整数之和。然后使用求和公式的逆公式计算出最大的整数`s`,使得从1到`s`的整数之和不超过`finalSum/2`。这是利用了求和公式的逆,通过解方程得到的。之后计算出1到`s`的整数之和,与`finalSum/2`的差值`res`就是最后一个需要添加的数。最终结果需要将这些整数转换回偶数,并添加到结果列表中。特别注意的是最后一个数是`(s + res) * 2`,这样确保了数列中的所有数都是唯一且符合要求的偶数。

时间复杂度:

O(s), 其中 s 是满足1到s的整数之和不超过finalSum/2的最大整数

空间复杂度:

O(s)

代码细节讲解

🦆
如何确定算法中使用的求和公式的逆公式是正确的,它是如何推导出来的?
算法中使用的求和公式是等差数列求和公式,即前n个自然数的和为n(n+1)/2。为了确定可以用哪个n值来接近但不超过finalSum/2,需要解方程n(n+1)/2 <= finalSum/2。这可以转化为求解二次方程n^2 + n - 2*finalSum/2 = 0。使用二次方程的求根公式(-b±sqrt(b^2-4ac))/2a),我们得到n = (-1 + sqrt(1 + 8*finalSum/2))/2。这里取负的根是不符合实际情况的,因为n应为正值,所以我们使用正的根。这就是求和公式的逆推导过程,确保了我们找到的最大整数s,使得从1到s的整数之和最接近但不超过finalSum/2。
🦆
在题解算法中计算出的最大整数s后,为什么可以断定从1到s的整数之和加上一个差值res就能满足题目要求?
在算法中,通过求和公式的逆公式首先计算出最大的整数s,使得从1到s的整数之和finalSum_2不超过finalSum/2。这保证了我们已经累积了尽可能多的连续整数总和。剩余的差值res = finalSum/2 - finalSum_2表示finalSum/2与1到s的和之间的差异。若添加这个差值作为下一个整数,即s+res,正好可以使总和达到finalSum/2。将这些整数转换为偶数后(即乘以2),确保了分解的偶数和为finalSum。这是因为每个连续整数乘以2得到的是连续偶数,且添加的最后一个偶数确保了总和达到原始的finalSum。
🦆
为什么在题解中将finalSum除以2后可以简化问题,这样的处理对最终结果的正确性有什么保证?
将finalSum除以2的原因是简化计算过程,因为原问题是将finalSum分解为多个不相同的偶数和。因为每一个偶数都是2的倍数,可以将每个偶数表示为2倍的一个整数(例如2, 4, 6表示为2×1, 2×2, 2×3)。因此,问题转化为将finalSum/2分解为若干个不相同的正整数的和。这样的处理简化了问题的复杂性,并且可以直接利用已知的数学公式(如等差数列求和)。最终将计算出的整数序列转换回偶数序列,并检查总和是否等于原始的finalSum,这确保了方法的正确性。因为每一步的转换和计算都保持了逻辑上的一致性和数学上的正确性。

相关问题