LeetCode 题解工作台
检查数组是否存在有效划分
给你一个下标从 0 开始的整数数组 nums ，你必须将数组划分为一个或多个 连续 子数组。 如果获得的这些子数组中每个都能满足下述条件 之一 ，则可以称其为数组的一种 有效 划分： 子数组 恰 由 2 个相等元素组成，例如，子数组 [2,2] 。 子数组 恰 由 3 个相等元素组成，例如，子数组 …
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们设计一个函数 ，表示从下标 开始是否存在一种有效划分。那么答案就是 。 函数 的执行过程如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个下标从 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 <= 1051 <= nums[i] <= 106
解题思路
方法一：记忆化搜索
我们设计一个函数 ，表示从下标 开始是否存在一种有效划分。那么答案就是 。
函数 的执行过程如下：
- 如果 ，返回 。
- 如果 和 下标的元素相等，那么可以选择将 和 作为一个子数组，递归调用 。
- 如果 , 和 下标的元素相等，那么可以选择将 , 和 作为一个子数组，递归调用 。
- 如果 , 和 下标的元素依次递增 ，那么可以选择将 , 和 作为一个子数组，递归调用 。
- 如果上述情况都不满足，返回 ，否则返回 。
即：
为了避免重复计算，我们使用记忆化搜索的方法。
时间复杂度 ，空间复杂度 。其中 为数组的长度。
class Solution:
def validPartition(self, nums: List[int]) -> bool:
@cache
def dfs(i: int) -> bool:
if i >= n:
return True
a = i + 1 < n and nums[i] == nums[i + 1]
b = i + 2 < n and nums[i] == nums[i + 1] == nums[i + 2]
c = (
i + 2 < n
and nums[i + 1] - nums[i] == 1
and nums[i + 2] - nums[i + 1] == 1
)
return (a and dfs(i + 2)) or ((b or c) and dfs(i + 3))
n = len(nums)
return dfs(0)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidates should demonstrate knowledge of dynamic programming state transitions and handling subarrays.
- question_mark
Look for candidates who can explain how smaller subarrays lead to valid partitions and how this problem is reduced to checking smaller subproblems.
- question_mark
Candidates should be able to identify the base case and how transitions occur from one state to another.
常见陷阱
外企场景- error
Forgetting to initialize the base case properly can lead to incorrect results.
- error
Overcomplicating the problem by not recognizing the simple state transitions between valid subarrays.
- error
Failing to handle the edge case of very small arrays properly can lead to unexpected outcomes.
进阶变体
外企场景- arrow_right_alt
Changing the condition of valid subarrays from equality to some other rule.
- arrow_right_alt
Introducing a constraint that subarrays must not only be valid but also sorted in a particular order.
- arrow_right_alt
Extending the problem to check for multiple valid partitions rather than just one.