2260.md

title	description	keywords
2260. 必须拿起的最小连续卡牌数	LeetCode 2260. 必须拿起的最小连续卡牌数题解，Minimum Consecutive Cards to Pick Up，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 2260. 必须拿起的最小连续卡牌数 必须拿起的最小连续卡牌数 Minimum Consecutive Cards to Pick Up 解题思路 数组 哈希表 滑动窗口

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

🟠 Medium  🔖  数组 哈希表 滑动窗口  🔗 力扣 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	无重复字符的最长子串	[✓]	哈希表 字符串 滑动窗口	🟠	🀄️ 🔗