Medium

题目描述

给你一个整数 finalSum。请你将它分割为 最多数量 的唯一正偶数之和。

例如，给定 finalSum = 12，以下分割是有效的（唯一正偶数求和等于 finalSum）：(12)、(2 + 10)、(2 + 4 + 6) 和 (4 + 8)。其中，(2 + 4 + 6) 包含最多的整数。注意 finalSum 不能分割为 (2 + 2 + 4 + 4) 因为所有的数字应该是唯一的。

返回表示有效分割的整数列表，该分割包含最多数量的整数。如果不存在有效的 finalSum 分割，则返回一个空列表。你可以按任何顺序返回这些整数。

示例 1：

输入：finalSum = 12
输出：[2,4,6]
解释：以下是有效分割：(12)、(2 + 10)、(2 + 4 + 6) 和 (4 + 8)。
(2 + 4 + 6) 有最多数量的整数，即 3 个。因此，我们返回 [2,4,6]。
注意 [2,6,4]、[6,2,4] 等也是可以接受的。

示例 2：

输入：finalSum = 7
输出：[]
解释：对于给定的 finalSum 没有有效分割。
因此，我们返回一个空数组。

示例 3：

输入：finalSum = 28
输出：[6,8,2,12]
解释：以下是有效分割：(2 + 26)、(6 + 8 + 2 + 12) 和 (4 + 24)。
(6 + 8 + 2 + 12) 有最多数量的整数，即 4 个。因此，我们返回 [6,8,2,12]。
注意 [10,2,4,12]、[6,2,4,16] 等也是可以接受的。

提示：

  • 1 <= finalSum <= 10^10

解题思路

这道题目要求我们将一个给定的数字分解为最多数量的不同正偶数之和。

核心思路：

首先，如果 finalSum 是奇数，那么不可能分解为偶数之和，直接返回空数组。

为了得到最多数量的偶数，我们应该贪心地使用最小的偶数。策略是从最小的正偶数开始依次选择：2, 4, 6, 8, …

算法步骤：

  1. 检查 finalSum 是否为偶数，如果不是则返回空数组
  2. 从 2 开始，依次选择连续的偶数：2, 4, 6, 8, …
  3. 继续选择直到剩余的数字小于下一个要选择的偶数
  4. 将剩余的数字加到最后一个选择的偶数上

举例说明：

  • finalSum = 12：选择 2, 4，剩余 6，直接加入 6，结果：[2, 4, 6]
  • finalSum = 28：选择 2, 4, 6, 8，剩余 8，但不能再选 10（会重复），所以将剩余的 8 加到最后的 8 上得到 16，但这样会减少数量。正确做法是将剩余部分分配给最后一个数字。

优化思路： 为了避免重复，当剩余数字等于下一个要选择的偶数时，我们将这部分加到最后一个已选择的数字上。

代码实现

class Solution {
public:
    vector<long long> maximumEvenSplit(long long finalSum) {
        if (finalSum % 2 == 1) {
            return {};
        }
        
        vector<long long> result;
        long long current = 2;
        
        while (finalSum >= current) {
            result.push_back(current);
            finalSum -= current;
            current += 2;
        }
        
        // 将剩余部分加到最后一个数字上
        if (!result.empty()) {
            result.back() += finalSum;
        }
        
        return result;
    }
};

class Solution:
    def maximumEvenSplit(self, finalSum: int) -> List[int]:
        if finalSum % 2 == 1:
            return []
        
        result = []
        current = 2
        
        while finalSum >= current:
            result.append(current)
            finalSum -= current
            current += 2
        
        # 将剩余部分加到最后一个数字上
        if result:
            result[-1] += finalSum
        
        return result

public class Solution {
    public IList<long> MaximumEvenSplit(long finalSum) {
        if (finalSum % 2 == 1) {
            return new List<long>();
        }
        
        List<long> result = new List<long>();
        long current = 2;
        
        while (finalSum >= current) {
            result.Add(current);
            finalSum -= current;
            current += 2;
        }
        
        // 将剩余部分加到最后一个数字上
        if (result.Count > 0) {
            result[result.Count - 1] += finalSum;
        }
        
        return result;
    }
}

/**
 * @param {number} finalSum
 * @return {number[]}
 */
var maximumEvenSplit = function(finalSum) {
    if (finalSum % 2 !== 0) {
        return [];
    }
    
    const result = [];
    let current = 2;
    let remaining = finalSum;
    
    while (remaining > 0) {
        if (remaining - current > current) {
            result.push(current);
            remaining -= current;
            current += 2;
        } else {
            result.push(remaining);
            break;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数值说明
时间复杂度O(√n)需要遍历约 √n 个连续偶数
空间复杂度O(√n)结果数组存储约 √n 个数字