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

难度: 中等

来源: 每日一题 2023.07.06

---

给你一个整数 finalSum 。请你将它拆分成若干个 互不相同 的正偶数之和，且拆分出来的正偶数数目 最多 。

比方说，给你 finalSum = 12 ，那么这些拆分是 符合要求 的（互不相同的正偶数且和为 finalSum）：(2 + 10) ，(2 + 4 + 6) 和 (4 + 8) 。它们中，(2 + 4 + 6) 包含最多数目的整数。注意 finalSum 不能拆分成 (2 + 2 + 4 + 4) ，因为拆分出来的整数必须互不相同。
请你返回一个整数数组，表示将整数拆分成 最多 数目的正偶数数组。如果没有办法将 finalSum 进行拆分，请你返回一个 空 数组。你可以按 任意 顺序返回这些整数。

示例 1：

输入：finalSum = 12
输出：[2,4,6]
解释：以下是一些符合要求的拆分：(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 <= 1010

class Solution {
    public List<Long> maximumEvenSplit(long finalSum) {

    }
}

分析与题解

---

• 贪心算法

  这个题目就是一顿遍历, 当然了,我们首先要处理边界条件,整体步骤如下所示.

  • 如果 finalSum 是 奇数, 直接返回空数组

  • 遍历 i 起始值为 2, 每一次加2, 边界条件就是 i < finalSum

  • finalSum 每次都要减去符合条件的值,不是一成不变的

  • 最后跳出遍历的时候, 不管 finalSum 的是什么数,添加到最后一个数上,肯定不会与数组中的任何数重复,并且偶数 + 偶数 肯定是 偶数. 这就是最终结果.

  整个解题过程如下所示.

  class Solution {
      public List<Long> maximumEvenSplit(long finalSum) {
          List<Long> result = new ArrayList<>();
  
          // 如果是奇数,直接返回为[]
          if ( finalSum%2 != 0) {
              return result;
          }
  
          for (int i = 2; i < finalSum; i += 2) {
              result.add(Long.ValueOf(i));
              // 计算finalSum剩余的值
              finalSum -= i;
          }
  
          // finalSum 最后剩余的值不管是否为0 都直接添加到数组的末尾
          result.set(result.size()-1, result.get(result.size()-1) + finalSum);
  
          return result;
      }
  }    
  

  复杂度分析:

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

  结果如下所示.