Leetcode刷题java之659. 分割数组为连续子序列（一天一道编程题之五十三天）

桃扇骨 2023-07-24 08:20 31阅读 0赞

执行结果：

通过

显示详情

执行用时 :36 ms, 在所有 Java 提交中击败了58.08% 的用户

内存消耗 :41.8 MB, 在所有 Java 提交中击败了50.00%

题目：

输入一个按升序排序的整数数组（可能包含重复数字），你需要将它们分割成几个子序列，其中每个子序列至少包含三个连续整数。返回你是否能做出这样的分割？

示例 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  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

采用贪心算法，优先和前面的组队，因为和后面的组队会出现单独的一个或者两个

另外代码中get方法改成getOrdefault方法，因为直接用get可能会空指针

代码：

class Solution {
        public boolean isPossible(int[] nums) {
            //用来记录每个数字出现的次数
            HashMap<Integer,Integer> numCount=new HashMap<>();
            //用来计算以这个数结尾的连续的次数
            HashMap<Integer,Integer> count=new HashMap<>();
            for(int num:nums)
            {
                numCount.put(num,numCount.getOrDefault(num,0)+1);
            }
            for(int num:nums)
            {
                //如果为0则跳过
                if(numCount.getOrDefault(num,0)==0)
                {
                    continue;
                    //如果大于0，并且前面有连续的，优先和前面组队，因为和后面组队
                    //和可能出现一个和两个的情况
                }else if(count.getOrDefault(num-1,0)>0)
                {
                    numCount.put(num,numCount.getOrDefault(num,0)-1);
                    count.put(num-1,count.getOrDefault(num-1,0)-1);
                    count.put(num,count.getOrDefault(num,0)+1);
                    //如果不能和前面组队，那么就和后面组队
                }else if(numCount.getOrDefault(num+1,0)>0&&numCount.getOrDefault(num+2,0)>0)
                {
                    numCount.put(num,numCount.getOrDefault(num,0)-1);
                    numCount.put(num+1,numCount.getOrDefault(num+1,0)-1);
                    numCount.put(num+2,numCount.getOrDefault(num+2,0)-1);
                    count.put(num+2,count.getOrDefault(num+2,0)+1);
                    //i前面和后面都不能组队，那么它指定是单独的了
                }else
                {
                    return false;
                }
            }
            return true;
        }
    }