跳转至

2811. 判断是否能拆分数组

题目描述

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

一个数组被称为 好 的，如果：

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

在每一步操作中，你可以选择一个 长度至少为 2 的现有数组（之前步骤的结果） 并将其拆分成 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

解释：

  • 将 [2, 3, 3, 2, 3] 切分为 [2] 和 [3, 3, 2, 3]。
  • 将 [3, 3, 2, 3] 切分为 [3, 3, 2] 和 [3]。
  • 将 [3, 3, 2] 切分为 [3, 3] 和 [2]。
  • 将 [3, 3] 切分为 [3] 和 [3]。

 

提示：

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

解法

方法一：记忆化搜索

我们先预处理得到前缀和数组 $s$，其中 $s[i]$ 表示数组 $nums$ 的前 $i$ 个元素之和。

接下来，我们设计一个函数 $dfs(i, j)$，表示对于数组 $nums$ 的下标范围 $[i, j]$，是否存在一种满足条件的拆分方法。如果存在，返回 true，否则返回 false。

函数 $dfs(i, j)$ 的计算过程如下：

如果 $i = j$，那么只有一个元素，不需要拆分，返回 true；

否则，我们枚举拆分点 $k$，其中 $k \in [i, j]$，如果满足以下条件，那么就可以拆分成 $nums[i,.. k]$ 和 $nums[k + 1,.. j]$ 两个子数组：

  • 子数组 $nums[i,..k]$ 只有一个元素，或者子数组 $nums[i,..k]$ 的元素之和大于等于 $m$；
  • 子数组 $nums[k + 1,..j]$ 只有一个元素，或者子数组 $nums[k + 1,..j]$ 的元素之和大于等于 $m$；
  • $dfs(i, k)$ 和 $dfs(k + 1, j)$ 都为 true。

为了避免重复计算，我们使用记忆化搜索的方法，用一个二维数组 $f$ 记录所有的 $dfs(i, j)$ 的返回值，其中 $f[i][j]$ 表示 $dfs(i, j)$ 的返回值。

时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$。其中 $n$ 是数组 $nums$ 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def canSplitArray(self, nums: List[int], m: int) -> bool:
        @cache
        def dfs(i: int, j: int) -> bool:
            if i == j:
                return True
            for k in range(i, j):
                a = k == i or s[k + 1] - s[i] >= m
                b = k == j - 1 or s[j + 1] - s[k + 1] >= m
                if a and b and dfs(i, k) and dfs(k + 1, j):
                    return True
            return False

        s = list(accumulate(nums, initial=0))
        return dfs(0, len(nums) - 1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    private Boolean[][] f;
    private int[] s;
    private int m;

    public boolean canSplitArray(List<Integer> nums, int m) {
        int n = nums.size();
        f = new Boolean[n][n];
        s = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            s[i] = s[i - 1] + nums.get(i - 1);
        }
        this.m = m;
        return dfs(0, n - 1);
    }

    private boolean dfs(int i, int j) {
        if (i == j) {
            return true;
        }
        if (f[i][j] != null) {
            return f[i][j];
        }
        for (int k = i; k < j; ++k) {
            boolean a = k == i || s[k + 1] - s[i] >= m;
            boolean b = k == j - 1 || s[j + 1] - s[k + 1] >= m;
            if (a && b && dfs(i, k) && dfs(k + 1, j)) {
                return f[i][j] = true;
            }
        }
        return f[i][j] = false;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    bool canSplitArray(vector<int>& nums, int m) {
        int n = nums.size();
        vector<int> s(n + 1);
        for (int i = 1; i <= n; ++i) {
            s[i] = s[i - 1] + nums[i - 1];
        }
        int f[n][n];
        memset(f, -1, sizeof f);
        function<bool(int, int)> dfs = [&](int i, int j) {
            if (i == j) {
                return true;
            }
            if (f[i][j] != -1) {
                return f[i][j] == 1;
            }
            for (int k = i; k < j; ++k) {
                bool a = k == i || s[k + 1] - s[i] >= m;
                bool b = k == j - 1 || s[j + 1] - s[k + 1] >= m;
                if (a && b && dfs(i, k) && dfs(k + 1, j)) {
                    f[i][j] = 1;
                    return true;
                }
            }
            f[i][j] = 0;
            return false;
        };
        return dfs(0, n - 1);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func canSplitArray(nums []int, m int) bool {
    n := len(nums)
    f := make([][]int, n)
    s := make([]int, n+1)
    for i, x := range nums {
        s[i+1] = s[i] + x
    }
    for i := range f {
        f[i] = make([]int, n)
    }
    var dfs func(i, j int) bool
    dfs = func(i, j int) bool {
        if i == j {
            return true
        }
        if f[i][j] != 0 {
            return f[i][j] == 1
        }
        for k := i; k < j; k++ {
            a := k == i || s[k+1]-s[i] >= m
            b := k == j-1 || s[j+1]-s[k+1] >= m
            if a && b && dfs(i, k) && dfs(k+1, j) {
                f[i][j] = 1
                return true
            }
        }
        f[i][j] = -1
        return false
    }
    return dfs(0, n-1)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function canSplitArray(nums: number[], m: number): boolean {
    const n = nums.length;
    const s: number[] = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; ++i) {
        s[i] = s[i - 1] + nums[i - 1];
    }
    const f: number[][] = Array(n)
        .fill(0)
        .map(() => Array(n).fill(-1));
    const dfs = (i: number, j: number): boolean => {
        if (i === j) {
            return true;
        }
        if (f[i][j] !== -1) {
            return f[i][j] === 1;
        }
        for (let k = i; k < j; ++k) {
            const a = k === i || s[k + 1] - s[i] >= m;
            const b = k === j - 1 || s[j + 1] - s[k + 1] >= m;
            if (a && b && dfs(i, k) && dfs(k + 1, j)) {
                f[i][j] = 1;
                return true;
            }
        }
        f[i][j] = 0;
        return false;
    };
    return dfs(0, n - 1);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
impl Solution {
    pub fn can_split_array(nums: Vec<i32>, m: i32) -> bool {
        let n = nums.len();
        if n <= 2 {
            return true;
        }
        for i in 1..n {
            if nums[i - 1] + nums[i] >= m {
                return true;
            }
        }
        false
    }
}

方法二：脑筋急转弯

不论如何操作，最终总会剩下一个 length == 2 的子数组，又因为元素数值不存在负数，所以随着分割操作的进行，子数组的长度和总和都会逐渐变小，其它 length > 2 子数组之和肯定要比该子数组之和更大，进而，我们只需要考虑，是否存在一个 length == 2 且总和大于等于 m 的子数组即可。

📢 注意，当 nums.length <= 2 时，无需进行操作。

时间复杂度 $O(n)$，其中 $n$ 是数组 $nums$ 的长度。空间复杂度 $O(1)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function canSplitArray(nums: number[], m: number): boolean {
    const n = nums.length;
    if (n <= 2) {
        return true;
    }
    for (let i = 1; i < n; i++) {
        if (nums[i - 1] + nums[i] >= m) {
            return true;
        }
    }
    return false;
}

评论