Medium

题目描述

给你一个长度为 n 的数组 nums 和一个整数 m。你需要判断是否可以通过一系列步骤将数组拆分成 n 个长度为 1 的数组。

一个数组被称为"好数组"当且仅当：

  • 数组的长度为 1，或者
  • 数组元素的和大于或等于 m

在每一步中，你可以选择一个现有的长度至少为 2 的数组（可能是之前步骤的结果），将其拆分为两个数组，前提是拆分后的两个数组都是好数组。

如果你能将给定数组拆分成 n 个数组，返回 true，否则返回 false。

示例 1：

输入：nums = [2, 2, 1], m = 4
输出：true
解释：
- 将 [2, 2, 1] 拆分为 [2, 2] 和 [1]。数组 [1] 长度为 1，数组 [2, 2] 元素和为 4 >= m，所以都是好数组。
- 将 [2, 2] 拆分为 [2] 和 [2]。两个数组长度都为 1，所以都是好数组。

示例 2：

输入：nums = [2, 1, 3], m = 5
输出：false
解释：
第一步必须是以下之一：
- 将 [2, 1, 3] 拆分为 [2, 1] 和 [3]。数组 [2, 1] 既不是长度为 1，元素和也不大于等于 m。
- 将 [2, 1, 3] 拆分为 [2] 和 [1, 3]。数组 [1, 3] 既不是长度为 1，元素和也不大于等于 m。
所以两种操作都无效，无法将 nums 拆分成 n 个长度为 1 的数组。

示例 3：

输入：nums = [2, 3, 3, 2, 3], m = 6
输出：true

约束：

  • 1 <= n == nums.length <= 100
  • 1 <= nums[i] <= 100
  • 1 <= m <= 200

解题思路

这道题的关键在于理解拆分的规则和找到关键的观察点。

核心观察： 通过分析拆分过程，我们可以发现一个重要规律：当数组长度大于 2 时，能否成功拆分主要取决于是否存在相邻元素对的和 ≥ m。

思路分析：

  1. 如果数组长度为 1 或 2，总是可以拆分成功（长度为 1 直接满足条件，长度为 2 可以拆分成两个长度为 1 的数组）
  2. 对于长度大于 2 的数组，我们需要在某个位置进行拆分，使得拆分后的两个子数组都是"好数组"
  3. 关键观察：如果存在相邻的两个元素 nums[i] + nums[i+1] >= m，那么我们总是可以成功拆分
  4. 这是因为我们可以将这两个相邻元素单独拆分出来作为一个子数组（满足和 ≥ m 的条件），剩余部分递归处理

算法步骤：

  • 特殊情况：如果数组长度 ≤ 2，直接返回 true
  • 遍历数组，检查是否存在相邻元素对的和 ≥ m
  • 如果存在，返回 true；如果不存在，返回 false

这个解法的正确性基于：当我们能够找到一个相邻对时，我们总能通过适当的拆分策略最终将数组完全拆分成单个元素。

代码实现

class Solution {
public:
    bool canSplitArray(vector<int>& nums, int m) {
        int n = nums.size();
        
        // 长度为1或2的数组总是可以拆分
        if (n <= 2) {
            return true;
        }
        
        // 检查是否存在相邻元素对的和 >= m
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] + nums[i + 1] >= m) {
                return true;
            }
        }
        
        return false;
    }
};

class Solution:
    def canSplitArray(self, nums: List[int], m: int) -> bool:
        n = len(nums)
        
        # 长度为1或2的数组总是可以拆分
        if n <= 2:
            return True
        
        # 检查是否存在相邻元素对的和 >= m
        for i in range(n - 1):
            if nums[i] + nums[i + 1] >= m:
                return True
        
        return False

public class Solution {
    public bool CanSplitArray(IList<int> nums, int m) {
        int n = nums.Count;
        
        // 长度为1或2的数组总是可以拆分
        if (n <= 2) {
            return true;
        }
        
        // 检查是否存在相邻元素对的和 >= m
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] + nums[i + 1] >= m) {
                return true;
            }
        }
        
        return false;
    }
}

var canSplitArray = function(nums, m) {
    const n = nums.length;
    
    // 长度为1或2的数组总是可以拆分
    if (n <= 2) {
        return true;
    }
    
    // 检查是否存在相邻元素对的和 >= m
    for (let i = 0; i < n - 1; i++) {
        if (nums[i] + nums[i + 1] >= m) {
            return true;
        }
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(1)

其中 n 为数组长度。算法只需要遍历一次数组检查相邻元素对，使用常数额外空间。