分割数组为连续子序列

给你一个按升序排序的整数数组 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

哈希表+贪心算法

哈希表统计每个数字的数量和以某个数字为结尾的序列的数量，
贪心序列中数字的数量，应越大越好（因为剩余的一个数字新建一个序列的失败可能性更大）

class Solution {
    public boolean isPossible(int[] nums) {
        
        Map<Integer, Integer> countMap = new HashMap<Integer, Integer>();//某个数字剩余的数量
        Map<Integer, Integer> endMap = new HashMap<Integer, Integer>();//以某个数字为结尾的序列的数量
        for (int x : nums) {//利用哈希表统计每个数字的数量
            int count = countMap.getOrDefault(x, 0) + 1;
            countMap.put(x, count);
        }
        for (int x : nums) {
            int count = countMap.getOrDefault(x, 0);
            if (count > 0) {//如果一个数字还没被用完
                int prevEndCount = endMap.getOrDefault(x - 1, 0);//查看以它前面的元素结尾的序列是否存在
                if (prevEndCount > 0) {//如果以它前面那个元素结尾的序列存在
                    countMap.put(x, count - 1);//将这个元素的数量减去1
                    endMap.put(x - 1, prevEndCount - 1);//以前面为结尾的序列的数量减去1
                    endMap.put(x, endMap.getOrDefault(x, 0) + 1);//以x为结尾的序列的数量加1
                } else {//如果以它前面的那个元素为结尾的序列不存在，那么这个元素是新序列的第一个元素，要想凑够3个元素
                    int count1 = countMap.getOrDefault(x + 1, 0);//后面的第一个元素的数量应该大于0
                    int count2 = countMap.getOrDefault(x + 2, 0);//后面的第二个元素的数量应该大于0
                    if (count1 > 0 && count2 > 0) {//如果后面的两个元素的数量都大于0，那么可以凑成
                        countMap.put(x, count - 1);
                        countMap.put(x + 1, count1 - 1);
                        countMap.put(x + 2, count2 - 1);
                        endMap.put(x + 2, endMap.getOrDefault(x + 2, 0) + 1);
                    } else {//后面的两个元素中有不大于0的，那么无法满足条件
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

参考文献

官方题解

赏

谢谢你请我吃糖果

微信