给你一个下标从 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
解释：该数组不存在有效划分。
动态规划
class Solution {
public:bool validPartition(vector<int>& nums) {int n = nums.size();vector<int> dp(n+1, 0);if(n == 2){return nums[1] == nums[0];}dp[0] = 1;dp[2] = nums[1] == nums[0];for(int i = 3; i < n+1; i++){if(nums[i-1] == nums[i-2]){dp[i] |= dp[i-2];}if(nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3]){dp[i] |= dp[i-3];}if(nums[i-1] == nums[i-2]+1 && nums[i-2] == nums[i-3]+1){dp[i] |= dp[i-3];}}return dp[n];}
};
时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们仅遍历一次 nums。
时间复杂度：O(n)。数组 dp 消耗 O(n)。
我们定义一个dp，用来储存在前i个元素中，是否有至少一个有效划分。我们在遍历过程中，一旦发现此时最近的几个元素，能够满足三种有效划分情况的一种，我们根据在这几个元素之前是否也存在有效划分，如果存在，那么说明目前至少存在一种有效划分。
最后返回dp[n]即可。
空间优化
class Solution {
public:bool validPartition(vector<int>& nums) {int n = nums.size();if (n == 2) {return nums[1] == nums[0];}// 只需要三个变量来存储之前的状态bool dp0 = true; // 对应于 dp[i-3]bool dp1 = false; // 对应于 dp[i-2]bool dp2 = nums[1] == nums[0]; // 对应于 dp[i-1]bool current = false; // 用于存储 dp[i] 的值for (int i = 3; i <= n; i++) {current = false;if (nums[i - 1] == nums[i - 2]) {current |= dp1;}if (nums[i - 1] == nums[i - 2] && nums[i - 2] == nums[i - 3]) {current |= dp0;}if (nums[i - 1] == nums[i - 2] + 1 && nums[i - 2] == nums[i - 3] + 1) {current |= dp0;}// 更新 dp0, dp1, dp2dp0 = dp1;dp1 = dp2;dp2 = current;}return current;}
};
空间压缩至O(1)
通过对未压缩代码观察，我们发现我们在动态规划状态转移过程中，最多只用到当前元素和前面两个元素，那么说明我们可以用三个变量来储存这些状态，然后在遍历nums的过程中不断覆盖滚动。
