说在前面
🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。
题目描述
给你一个长度为 n 的整数数组 rolls 和一个整数 k 。你扔一个 k 面的骰子 n 次，骰子的每个面分别是 1 到 k ，其中第 i 次扔得到的数字是 rolls[i] 。
请你返回 无法 从 rolls 中得到的 最短 骰子子序列的长度。
扔一个 k 面的骰子 len 次得到的是一个长度为 len 的 骰子子序列 。
注意 ，子序列只需要保持在原数组中的顺序，不需要连续。
示例 1：
输入：rolls = [4,2,1,2,3,3,2,4,1], k = 4 输出：3 解释：所有长度为 1 的骰子子序列 [1] ，[2] ，[3] ，[4] 都可以从原数组中得到。 所有长度为 2 的骰子子序列 [1, 1] ，[1, 2] ，... ，[4, 4] 都可以从原数组中得到。 子序列 [1, 4, 2] 无法从原数组中得到，所以我们返回 3 。 还有别的子序列也无法从原数组中得到。
示例 2：
输入：rolls = [1,1,2,2], k = 2 输出：2 解释：所有长度为 1 的子序列 [1] ，[2] 都可以从原数组中得到。 子序列 [2, 1] 无法从原数组中得到，所以我们返回 2 。 还有别的子序列也无法从原数组中得到，但 [2, 1] 是最短的子序列。
示例 3：
输入：rolls = [1,1,3,2,2,2,3,3], k = 4 输出：1 解释：子序列 [4] 无法从原数组中得到，所以我们返回 1 。 还有别的子序列也无法从原数组中得到，但 [4] 是最短的子序列。
提示：
n == rolls.length 1 <= n <= 10^5 1 <= rolls[i] <= k <= 10^5
思路分析
今天的这道题目是一道思维题，乍一看没有思路就会感觉是一道很困难的题目，但当你看透了题目的本质之后，你就会恍然大悟。
从题目中我们可以知道这里的一枚骰子有k个面，所以其结果可能为1~k，如果取子序列长度为1的话，即每一个面的结果都应该至少出现一次，最理想的结果如上图，每个结果都出现一次。
接下来我们再看一下长度为2的情况，其实和长度为1的子序列是类似的，每一个位置上的取值都有1~k，看到这里是不是有了思路了？
所以在原序列rolls中取子序列时，我们可以这样做，如上图，我们看将rolls序列划分成多段包含k种结果的数组段，这样我们在每一段中都可以取到1~k的值，所以我们只需要统计数组可以划分的段数，即可得出可能得到的最长骰子序列，反之也即得到了可能得到的最短骰子序列
AC代码
/** * @param {number[]} rolls * @param {number} k * @return {number} */ var shortestSequence = function(rolls, k) { let res = 1; let set = new Set(); for(let i = 0; i < rolls.length; i++){ set.add(rolls[i]); if(set.size == k) { res++; set = new Set(); } } return res; };
公众号
关注公众号『前端也能这么有趣』，获取更多有趣内容。
说在后面
🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『
前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。
