# Split Array into Consecutive Subsequences问题及解法

xiaoxiao2021-02-28  26

You are given an integer array sorted in ascending order (may contain duplicates), you need to split them into several subsequences, where each subsequences consist of at least 3 consecutive integers. Return whether you can make such a split.

Input: [1,2,3,3,4,5] Output: True Explanation: You can split them into two consecutive subsequences : 1, 2, 3 3, 4, 5 Input: [1,2,3,3,4,4,5,5] Output: True Explanation: You can split them into two consecutive subsequences : 1, 2, 3, 4, 5 3, 4, 5 Input: [1,2,3,4,4,5] Output: False

Note:

The length of the input is in range of [1, 10000]

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