Every day a Leetcode

題目來源：659. 分割數組為連續子序列

解法1：哈希 + 貪心

定義兩個哈希表：

• numsCount：統計數組 nums 中各元素出現次數。
• tailCount：存儲以數字 i 結尾的且符合題意的連續子序列個數。

算法：

1. 先去尋找一個長度為3的連續子序列 i，i+1，i+2，找到后就將 numsCount[i]，numsCount[i+1]，numsCount[i+2] 中對應數字消耗 1 個（即 -1），并將 tail[i+2] 加 1，即以 i+2 結尾的子序列個數 +1。
2. 如果后續發現有能夠接在這個連續子序列的數字 i+3，則延長以 i+2 為結尾的連續子序列到 i+3，此時消耗 numsCount[i+3] 一個，由于子序列已延長，因此 tailCount[i+2] 減 1，tailCount[i+3] 加 1。
3. 在不滿足上面的情況下：
   • 如果 numsCount[i] == 0，說明這個數字已經消耗完，可以不管了。
   • 如果 numsCount[i] != 0，說明這個數字多出來了，且無法組成連續子序列，直接返回 false。

因此，只有檢查到某個數時，這個數未被消耗完，且既不能和前面組成連續子序列，也不能和后面組成連續子序列時，無法分割。

關于上面 1 和 2 的優先度，也就是說，當遇到一個新數，是新建一個長度為 3 的子序列好，還是補充到原有子序列的末尾好？

優先開新序列，不夠貪，會丟失部分子序列尾的位置，而這可能造成丟解。

優先補前面更貪心，這種做法會覆蓋優先開新序列時的尾的位置，補這補這總能到，補的過程中出現的尾位置也不會丟失。

代碼：

/** @lc app=leetcode.cn id=659 lang=cpp** [659] 分割數組為連續子序列*/// @lc code=start
class Solution
{
public:bool isPossible(vector<int> &nums){if (nums.size() < 3)return false;unordered_map<int, int> numsCount, tailCount;// 統計數組 nums 中各元素出現次數for (int &num : nums)numsCount[num]++;// tailCount[i] 表示以 i 結尾的符合條件的子序列個數for (int &num : nums){if (numsCount[num] == 0)continue;else if (numsCount[num] > 0 && tailCount[num - 1] > 0){// 1. 補充到已有子序列的尾部numsCount[num] -= 1;tailCount[num - 1] -= 1;tailCount[num] += 1;}else if (numsCount[num] > 0 && numsCount[num + 1] > 0 && numsCount[num + 2] > 0){// 2. 新建一條長度為 3 的子序列// 注意 1 的優先級比 2 高numsCount[num] -= 1;numsCount[num + 1] -= 1;numsCount[num + 2] -= 1;tailCount[num + 2] += 1;}elsereturn false;}return true;}
};
// @lc code=end

結果：

復雜度分析：

時間復雜度：O(n)，其中 n 是數組 nums 的長度。

空間復雜度：O(n)，其中 n 是數組 nums 的長度。