Skip to content

Latest commit

 

History

History

659.Split-Array-into-Consecutive-Subsequences

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

659.Split-Array-into-Consecutive-Subsequences

假设我们当前处理的数字是x。下面分两种情况讨论:

如果之前的处理过的元素里,已经有以x-1为结尾的、长度大于等于3的序列,那么我们必然会将x接在这个已有的序列上。为什么呢?如果我们不接,那么x必然是作为一段新序列的首元素。但是如果后面没有x+1和x+2接上,那么x这个新序列就无法满足长度要求。而如果后面有x+1和x+2,那么我们何不将x,x+1,x+2一并都接在以x-1为结尾的序列上呢?可见不管后面是否有x+1/x+2,将x接在已有的序列上,都是最保险的决策。

如果之前的处理过的元素里,已经有以x-1为结尾的、长度大于等于3的序列,那么我们该怎么办呢?我们就必须创建以x为首元素的新序列,同时为了保证该新序列的最终长度要大于等于3,我们必须向后面“预支”两个元素:x+1和x+2。如果我们能提前知道后面已经没有了x+1和x+2,那么我们就可以返回false。

所以我们需要两个哈希表。seq[x]表示目前为止已经构建了多少个以x为结尾的、长度大于等于3的序列。left[x]表示后面还有多少个x没有被处理(初始值就是原数组中的x的个数)。当第一种情况时,以x-1结尾的序列会变成以一个新的以x为结尾的序列。第二种情况时,会增加一个以x+2为结尾的序列,同时注意相应的left[x],left[x+1],left[x+2]都需要自减1.

Leetcode Link