2811-判断是否能拆分数组

给你一个长度为 n 的数组 nums 和一个整数 m 。请你判断能否执行一系列操作，将数组拆分成 n 个 非空 数组。

在每一步操作中，你可以选择一个 长度至少为 2 的现有数组（之前步骤的结果） 并将其拆分成 2 个子数组，而得到的 每个 子数组，
至少 需要满足以下条件之一：

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

如果你可以将给定数组拆分成 n 个满足要求的数组，返回 true __ ；否则，返回 false 。

注意： 子数组是数组中的一个连续非空元素序列。

示例 1：

**输入：** nums = [2, 2, 1], m = 4
**输出：** true
**解释：**
第 1 步，将数组 nums 拆分成 [2, 2] 和 [1] 。
第 2 步，将数组 [2, 2] 拆分成 [2] 和 [2] 。
因此，答案为 true 。

示例 2：

**输入：** nums = [2, 1, 3], m = 5 
**输出：** false
**解释：** 存在两种不同的拆分方法：
第 1 种，将数组 nums 拆分成 [2, 1] 和 [3] 。
第 2 种，将数组 nums 拆分成 [2] 和 [1, 3] 。
然而，这两种方法都不满足题意。因此，答案为 false 。

示例 3：

**输入：** nums = [2, 3, 3, 2, 3], m = 6
**输出：** true
**解释：**
第 1 步，将数组 nums 拆分成 [2, 3, 3, 2] 和 [3] 。
第 2 步，将数组 [2, 3, 3, 2] 拆分成 [2, 3, 3] 和 [2] 。
第 3 步，将数组 [2, 3, 3] 拆分成 [2] 和 [3, 3] 。
第 4 步，将数组 [3, 3] 拆分成 [3] 和 [3] 。
因此，答案为 true 。 

提示：

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

请看 视频讲解 第二题。

先特判 n\le 2 的情况，这是满足要求的。

对于 n\ge 3 的情况，无论按照何种方式分割，一定会在某个时刻，分割出一个长为 2 的子数组。

如果 nums 中任何长为 2 的子数组的元素和都小于 m，那么无法满足要求。

否则，可以用这个子数组作为「核心」，像剥洋葱一样，一个一个地去掉 nums 的首尾元素，最后得到这个子数组。由于子数组的元素和 \ge m，所以每次分割出一个元素时，剩余的子数组的元素和也必然是 \ge m 的，满足要求。

所以问题变成：判断数组中是否有两个相邻数字 \ge m。

[sol-Python3]

class Solution:
    def canSplitArray(self, nums: List[int], m: int) -> bool:
        return len(nums) <= 2 or any(x + y >= m for x, y in pairwise(nums))

[sol-Java]

class Solution {
    public boolean canSplitArray(List<Integer> nums, int m) {
        int n = nums.size();
        if (n <= 2) return true;
        for (int i = 1; i < n; i++)
            if (nums.get(i - 1) + nums.get(i) >= m)
                return true;
        return false;
    }
}

[sol-C++]

class Solution {
public:
    bool canSplitArray(vector<int> &nums, int m) {
        int n = nums.size();
        if (n <= 2) return true;
        for (int i = 1; i < n; i++)
            if (nums[i - 1] + nums[i] >= m)
                return true;
        return false;
    }
};

[sol-Go]

func canSplitArray(nums []int, m int) bool {
	n := len(nums)
	if n <= 2 {
		return true
	}
	for i := 1; i < n; i++ {
		if nums[i-1]+nums[i] >= m {
			return true
		}
	}
	return false
}

复杂度分析

• 时间复杂度：\mathcal{O}(n)，其中 n 为 nums 的长度。
• 空间复杂度：\mathcal{O}(1)。仅用到若干额外变量。