2369. 檢查數組是否存在有效劃分

題目描述：

給你一個下標從?0?開始的整數數組?nums?，你必須將數組劃分為一個或多個?連續?子數組。

如果獲得的這些子數組中每個都能滿足下述條件?之一?，則可以稱其為數組的一種?有效?劃分：

1. 子數組?恰?由?2?個相等元素組成，例如，子數組?[2,2]?。
2. 子數組?恰?由?3?個相等元素組成，例如，子數組?[4,4,4]?。
3. 子數組?恰?由?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^5
• 1 <= nums[i] <= 10^6

思路：

感覺子串的題很多都是滑動窗口？

這一二條有重合的部分，想象如果滿足二必定滿足一，所以只需要判斷一是否滿足，如果是，則直接跳出；不滿足一也不可能滿足二，直接不用判斷條件二了；一判斷結束，開始判斷三。

沒試出來，直奔題解，哦，dp

代碼：

class Solution {public boolean validPartition(int[] nums) {int n =nums.length;boolean[] f=new boolean[n+1];f[0]=true;for(int i=1;i<n;i++){if (f[i - 1] && nums[i] == nums[i - 1] ||i > 1 && f[i - 2] && (nums[i] == nums[i - 1] && nums[i] == nums[i - 2] ||nums[i] == nums[i - 1] + 1 && nums[i] == nums[i - 2] + 2)) {f[i + 1] = true;}}return f[n];}
}