Вам дан 0-индексированный массив целых чисел nums. Вы должны разделить массив на один или несколько непрерывных подмассивов.

Мы называем разбиение массива действительным, если каждый из полученных подмассивов удовлетворяет одному из следующих условий:

  1. Подмассив состоит из ровно 2 одинаковых элементов. Например, подмассив [2,2] хорош.
  2. Подмассив состоит из точно 3 одинаковых элементов. Например, подмассив [4,4,4] хорош.
  3. Подмассив состоит из ровно 3 последовательных возрастающих элементов, то есть разница между соседними элементами составляет 1. Например, подмассив [3,4,5] хорош, а подмассив [1,3,5] — нет.

Вернуть true, если массив имеет по крайней мере один действительный раздел. В противном случае вернуть false.

Пример 1:

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.

Пример 2:

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

Ограничения:

  • 2 <= nums.length <= 105
  • 1 <= nums[i] <= 106
class Solution {
public:
    bool solve(vector<int> &nums, vector<int> &dp, int i){
        int n=nums.size();
        if(i==n) return true;
        
        if(dp[i]!=-1) return dp[i];
        
        bool res=false;
        
        if(i+1<n && nums[i]==nums[i+1]){
            res=solve(nums, dp, i+2);
            if(i+2<n && nums[i]==nums[i+2]){
                res=res|| solve(nums, dp, i+3);
            }
        }
        
        if(i+2<n && nums[i+1]-nums[i]==1 && nums[i+2]-nums[i+1]==1){
            res=res|| solve(nums, dp, i+3);
        }
        
        return dp[i]=res;
    }
    bool validPartition(vector<int>& nums) {
        int n=nums.size();
        if(n==2){
            if(nums[0]==nums[1]) return true;
        }
        vector<int> dp(n, -1);
        return solve(nums, dp, 0);
    }
};

Изначально, если длина массива или размер nums равны 2, то возможен только один случай, когда он возвращает true, т.е. nums[0]==nums[1], таким образом, оба являются равными элементами, а для остальных применяется DP :)

Пример 1

Проверьте наличие двух последовательных равных элементов, если они равны, затем сделайте еще один вызов для дальнейшей проверки в массиве, это делается DP, поэтому напряжение не … только проверьте nums [i] == nums [i + 1]… & make res = true и далее проверьте три последовательных одинаковых элемента, если они равны, затем сделайте еще один вызов для дальнейшей проверки в этом массиве, это делается DP.

разрешение = разрешение || solve( — ) // в этом res будет установлено значение true, если первые 2 элемента равны, затем проверьте дальнейший вызов.

Если все I случай и II случай не работают, проверьте для III случая 3 возрастающих числа.

Пример 2

Спасибо !! Счастливого обучения :)