2260. 必须拿起的最小连续卡牌数

🟠   🔖  数组 哈希表 滑动窗口  🔗 力扣 LeetCode

题目

You are given an integer array cards where cards[i] represents the value of the ith card. A pair of cards are matching if the cards have the same value.

Return the minimum number of consecutive cards you have to pick up to have a pair of matching cards among the picked cards. If it is impossible to have matching cards, return -1.

Example 1:

Input: cards = [3,4,2,3,4,7]

Output: 4

Explanation: We can pick up the cards [3,4,2,3] which contain a matching pair of cards with value 3. Note that picking up the cards [4,2,3,4] is also optimal.

Example 2:

Input: cards = [1,0,5,3]

Output: -1

Explanation: There is no way to pick up a set of consecutive cards that contain a pair of matching cards.

Constraints:

• 1 <= cards.length <= 10^5
• 0 <= cards[i] <= 10^6

题目大意

给你一个整数数组 cards ，其中 cards[i] 表示第 i 张卡牌的 值 。如果两张卡牌的值相同，则认为这一对卡牌 匹配 。

返回你必须拿起的最小连续卡牌数，以使在拿起的卡牌中有一对匹配的卡牌。如果无法得到一对匹配的卡牌，返回 -1 。

解题思路

可以使用滑动窗口来解决这道题。

• 用一个 Map 来存储滑动窗口内的数；
• 初始化返回值 res 为 cards.length + 1，方便判断最后能否得到一对匹配的卡牌，若有匹配的卡片，res 可能的最大值为 cards.length；
• 向右扩大右边界，判断窗口内是否已经包含当前数：
  • 若不包含，则将卡牌放入窗口里；
  • 若已经包含，则找到了一对匹配的卡牌，更新 res 为最小值，同时缩小左窗口，也即更新 Map 中的值为当前位置；
• 遍历完之后，返回 res

这道题与一般滑动窗口题不一样的地方是，缩小左边界是隐式地更新 Map 完成的，详细的滑动窗口答题框架讲解，可阅读 《3.11 滑动窗口》。

代码

/**
 * @param {number[]} cards
 * @return {number}
 */
var minimumCardPickup = function (cards) {
	let i = 0,
		n = cards.length,
		res = n + 1,
		window = new Map();
	while (i < n) {
		let card = cards[i];
		if (window.has(card)) {
			res = Math.min(res, i - window.get(card) + 1);
		}
		window.set(card, i);
		i++;
	}
	return res == n + 1 ? -1 : res;
};

相关题目

题号	标题	题解	标签	难度
3	无重复字符的最长子串	[✓]	哈希表 字符串 滑动窗口