LeetCode：659. Split Array into Consecutive Subsequences分割数组为连续子序列（C语言）

清疚 2022-12-26 10:13 90阅读 0赞

**题目描述：**  
给你一个按升序排序的整数数组 num（可能包含重复数字），请你将它们分割成一个或多个子序列，其中每个子序列都由连续整数组成且长度至少为 3 。

如果可以完成上述分割，则返回 true ；否则，返回 false 。

示例 1：

输入: \[1,2,3,3,4,5\]  
输出: True  
解释:  
你可以分割出这样两个连续子序列 :  
1, 2, 3  
3, 4, 5

示例 2：

输入: \[1,2,3,3,4,4,5,5\]  
输出: True  
解释:  
你可以分割出这样两个连续子序列 :  
1, 2, 3, 4, 5  
3, 4, 5

示例 3：

输入: \[1,2,3,4,4,5\]  
输出: False

提示：

输入的数组长度范围为 [1, 10000]

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/split-array-into-consecutive-subsequences  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。  
**解答：**

struct hashTable { 
        int key;
        int val;
        UT_hash_handle hh;
    };
    
    struct hashTable* find(struct hashTable** hashtable, int ikey) { 
        struct hashTable* tmp;
        HASH_FIND_INT(*hashtable, &ikey, tmp);
        return tmp;
    }
    
    void insert(struct hashTable** hashtable, int ikey, int ival) { 
        struct hashTable* tmp = malloc(sizeof(struct hashTable));
        tmp->key = ikey, tmp->val = ival;
        HASH_ADD_INT(*hashtable, key, tmp);
    }
    
    int query(struct hashTable** hashtable, int ikey) { 
        struct hashTable* tmp;
        HASH_FIND_INT(*hashtable, &ikey, tmp);
        if (tmp == NULL) { 
            return 0;
        }
        return tmp->val;
    }
    
    void modify(struct hashTable** hashtable, int ikey, int ival) { 
        struct hashTable* tmp = find(hashtable, ikey);
        if (tmp == NULL) { 
            insert(hashtable, ikey, ival);
        } else { 
            tmp->val = ival;
        }
    }
    
    void inc(struct hashTable** hashtable, int ikey) { 
        struct hashTable* tmp = find(hashtable, ikey);
        if (tmp == NULL) { 
            insert(hashtable, ikey, 1);
        } else { 
            tmp->val++;
        }
    }
    
    bool isPossible(int* nums, int numsSize) { 
        struct hashTable* countMap = NULL;
        struct hashTable* endMap = NULL;
        for (int i = 0; i < numsSize; i++) { 
            inc(&countMap, nums[i]);
        }
        for (int i = 0; i < numsSize; i++) { 
            int count = query(&countMap, nums[i]);
            if (count > 0) { 
                int prevEndCount = query(&endMap, nums[i] - 1);
                if (prevEndCount > 0) { 
                    modify(&countMap, nums[i], count - 1);
                    modify(&endMap, nums[i] - 1, prevEndCount - 1);
                    inc(&endMap, nums[i]);
                } else { 
                    int count1 = query(&countMap, nums[i] + 1);
                    int count2 = query(&countMap, nums[i] + 2);
                    if (count1 > 0 && count2 > 0) { 
                        modify(&countMap, nums[i], count - 1);
                        modify(&countMap, nums[i] + 1, count1 - 1);
                        modify(&countMap, nums[i] + 2, count2 - 1);
                        inc(&endMap, nums[i] + 2);
                    } else { 
                        return false;
                    }
                }
            }
        }
        return true;
    }

**运行结果：**  
![在这里插入图片描述][20201204150024331.png_pic_center]

**Notes：**  
参考的是官方解答。

[20201204150024331.png_pic_center]: /images/20221120/a1e384eef5ee42c89e9e58f940fdb912.png