检查数组是否存在有效划分

难度: Medium

给你一个下标从 0 开始的整数数组 nums ，你必须将数组划分为一个或多个连续子数组。

如果获得的这些子数组中每个都能满足下述条件之一，则可以称其为数组的一种有效划分：

子数组恰由 2 个相等元素组成，例如，子数组 [2,2] 。
子数组恰由 3 个相等元素组成，例如，子数组 [4,4,4] 。
子数组恰由 3 个连续递增元素组成，并且相邻元素之间的差值为 1 。例如，子数组 [3,4,5] ，但是子数组 [1,3,5] 不符合要求。

如果数组至少存在一种有效划分，返回 true ，否则，返回 false 。

示例 1：

输入：nums = [4,4,4,5,6]
输出：true
解释：数组可以划分成子数组 [4,4] 和 [4,5,6] 。
这是一种有效划分，所以返回 true 。

示例 2：

输入：nums = [1,1,1,2]
输出：false
解释：该数组不存在有效划分。

提示：

2 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁶

Submission

运行时间: 66 ms

内存: 50.0 MB

class Solution:
    def validPartition(self, nums: List[int]) -> bool:
        # f[i] 前i个数字能否有效划分
        # f[i] = (i >= 2 and nums[i-1] == nums[i-2] and f[i-2]) or (i >= 3 and nums[i-1] == nums[i-2] == nums[i-3] and f[i-3]) or (i >= 3 and nums[i-3]+2 == nums[i-2]+1 == nums[i-1] and f[i-3])
        # basecase f[0] = True
        n = len(nums)
        def f(i):
            if i < 0: return False
            if i == 0: return True
            if (i >= 2 and nums[i-1] == nums[i-2] and f(i-2)) or (i >= 3 and nums[i-1] == nums[i-2] == nums[i-3] and f(i-3)) or (i >= 3 and nums[i-3]+2 == nums[i-2]+1 == nums[i-1] and f(i-3)):
                return True
            return False
        return f(len(nums))

Explain

本题解使用了动态规划的方法来解决问题。定义一个动态规划数组f，其中f[i]表示数组nums的前i个元素是否可以被有效地划分。动态规划的转移方程考虑了三种情况：1) 最后两个元素是相等的，即构成了一个有效的两元素子数组；2) 最后三个元素是相等的，即构成了一个有效的三元素子数组；3) 最后三个元素是连续递增的，即形成了一个有效的三元素子数组。如果任意一种情况成立，并且剩余的前面的元素也可以有效划分（即f[i-2]或f[i-3]为真），则f[i]为真。递归地检查直到数组末尾，以确定整个数组是否可以有效划分。

时间复杂度: O(2^n)

空间复杂度: O(n)

class Solution:
    def validPartition(self, nums: List[int]) -> bool:
        # 动态规划函数，用于判断前i个元素是否可以有效划分
        def f(i):
            if i < 0: return False  # 如果小于0，无法形成子数组
            if i == 0: return True  # 空数组默认是有效的划分
            # 检查三种有效划分的情况
            if (i >= 2 and nums[i-1] == nums[i-2] and f(i-2)) or \
               (i >= 3 and nums[i-1] == nums[i-2] == nums[i-3] and f(i-3)) or \
               (i >= 3 and nums[i-3]+2 == nums[i-2]+1 == nums[i-1] and f(i-3)):
                return True
            return False
        # 从整个数组的长度开始递归判断
        return f(len(nums))

Explore

在动态规划解法中，将i=0时视为有效划分是因为它代表一个空数组，而空数组是可以被视作有效划分，因为它没有元素需要被划分。这是一个边界条件，用于确保递归过程中在i减去2或3后，当索引i达到0时能够有一个基本的返回值。这样的处理方式简化了代码逻辑，并避免了对空数组特殊情况的额外处理。

这种判断方式是为了确认数组中的这三个数字是否形成了递增的连续整数序列。具体来说，nums[i-3], nums[i-2], nums[i-1] 如果是连续递增的，则nums[i-2]应该比nums[i-3]大1，nums[i-1]应该比nums[i-2]大1。因此，如果nums[i-3]+2等于nums[i-1]，同时nums[i-2]+1等于nums[i-1]，则这三个数形成了连续递增的序列。这是检查连续递增序列的一种数学上简洁的方法。

是的，当i<2时，数组中的元素数量不足以形成有效的两元素或三元素子数组。因此，当i<2时，理论上不存在有效的划分方式。在函数实现中，当i=1时，由于无法形成任何规定的子数组模式，f(1)也应该返回False。在i=0时返回True是为了处理空数组的特殊情况。

在没有使用备忘录或其他优化措施的情况下，递归实现的效率可能会较低。因为在递归过程中，相同的状态（即相同的i值）可能会被重复计算多次，导致大量的重复工作。这会显著增加时间复杂度，尤其是在nums数组较大时。理想情况下，使用备忘录或者迭代的动态规划方法可以有效减少重复计算，提高算法的效率。