Tách mảng thành các dãy con liên tiếp trong C++

Cho mảng nums đã sắp xếp tăng dần. Xác định có thể chia thành một hoặc nhiều dãy con liên tiếp (mỗi dãy độ dài ≥ 3) hay không.

Ví dụ: [1,2,3,3,4,4,5,5] → true (chia thành [1,2,3,4,5] và [3,4,5]).

Thuật toán (Tham lam + Hash Map)

1. Đếm tần suất mỗi số trong map m.
2. Duyệt mảng, với mỗi x = nums[i] nếu còn x, x+1, x+2 thì tạo dãy mới:
3. Giảm tần suất x, x+1, x+2, mở rộng dãy bằng cách thêm x+3, x+4... miễn là tần suất cho phép.
4. Cuối cùng kiểm tra tất cả phần tử đã được dùng (cnt == 0).

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool isPossible(vector<int>& nums) {
        unordered_map<int, int> m;
        int n = nums.size();
        for (int x : nums) m[x]++;
        int cnt = n;
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            if (m[x] && m[x+1] && m[x+2]) {
                m[x]--; m[x+1]--; m[x+2]--;
                x += 3; cnt -= 3;
                while (m[x] > 0 && m[x] > m[x-1]) {
                    m[x]--; cnt--; x++;
                }
            }
        }
        return cnt == 0;
    }
};

int main() {
    vector<int> v = {1,2,3,3,4,4,5,5};
    Solution ob;
    cout << ob.isPossible(v);
    return 0;
}

Đầu vào / Đầu ra

Input: [1,2,3,3,4,4,5,5]

Output: 1 (true)