check-if-there-is-a-valid-partition-for-the-array

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a 0-indexed integer array <code>nums</code>. You have to partition the array into one or more contiguous subarrays.

We call a partition of the array valid if each of the obtained subarrays satisfies one of the following conditions:

<ol>
	<li>The subarray consists of exactly <code>2,</code> equal elements. For example, the subarray <code>[2,2]</code> is good.</li>
	<li>The subarray consists of exactly <code>3,</code> equal elements. For example, the subarray <code>[4,4,4]</code> is good.</li>
	<li>The subarray consists of exactly <code>3</code> consecutive increasing elements, that is, the difference between adjacent elements is <code>1</code>. For example, the subarray <code>[3,4,5]</code> is good, but the subarray <code>[1,3,5]</code> is not.</li>
</ol>

Return <code>true</code> if the array has at least one valid partition. Otherwise, return <code>false</code>.

&nbsp;
Example 1:

<pre>
Input: nums = [4,4,4,5,6]
Output: true
Explanation: The array can be partitioned into the subarrays [4,4] and [4,5,6].
This partition is valid, so we return true.
</pre>

Example 2:

<pre>
Input: nums = [1,1,1,2]
Output: false
Explanation: There is no valid partition for this array.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 106</code></li>
</ul>

validPartition

Check if There is a Valid Partition For The Array

Count the Number of Good Partitions

count-the-number-of-good-partitions

统计好分割方案的数目

Array

Dynamic Programming

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

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

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

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

&nbsp;

示例 1：

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

示例 2：

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

&nbsp;

提示：

<ul>
	<li><code>2 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 106</code></li>
</ul>