What is the key idea for Minimum Consecutive Cards to Pick Up?

Track the last index of every card value in a hash map. When a value appears again, compute the consecutive pickup length from the previous index to the current one and keep the minimum.

Why is the most recent previous index the right one to use?

For a fixed current index, the nearest previous equal card creates the shortest possible segment ending there. Any older equal card would produce a longer consecutive pickup.

Is this really a sliding window problem?

It is often tagged with Sliding Window, but the clean solution is array scanning plus hash lookup. You do not need to grow and shrink a window because a duplicate immediately defines the only segment length that matters at that step.

Why does cards = [3,4,2,3,4,7] return 4?

The repeated 3 appears at indices 0 and 3, so that span has length 4. The repeated 4 at indices 1 and 4 also gives length 4, and no shorter duplicate span exists.

What should I return if no value repeats?

Return -1. If the scan finishes without finding any card value already in the hash map, no consecutive block can contain a matching pair.

#2260

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

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

给你一个整数数组 cards ，其中 cards[i] 表示第 i 张卡牌的值。如果两张卡牌的值相同，则认为这一对卡牌匹配。返回你必须拿起的最小连续卡牌数，以使在拿起的卡牌中有一对匹配的卡牌。如果无法得到一对匹配的卡牌，返回 -1 。示例 1：输入： cards = [3,4,2,3,…

数组哈希表滑动窗口

题目描述

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

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

示例 1：

输入：cards = [3,4,2,3,4,7]
输出：4
解释：拿起卡牌 [3,4,2,3] 将会包含一对值为 3 的匹配卡牌。注意，拿起 [4,2,3,4] 也是最优方案。

示例 2：

输入：cards = [1,0,5,3]
输出：-1
解释：无法找出含一对匹配卡牌的一组连续卡牌。

提示：

1 <= cards.length <= 10⁵
0 <= cards[i] <= 10⁶

lightbulb

解题思路

方法一：哈希表

我们初始化答案为 $+\infty$ ，遍历数组，对于每个数字 $x$ ，如果 $\textit{last}[x]$ 存在，则表示 $x$ 有一对匹配卡牌，此时更新答案为 $\textit{ans} = \min(\textit{ans}, i - \textit{last}[x] + 1)$ ，最后如果答案为 $+\infty$ ，则返回 $-1$ ，否则返回答案。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组长度。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def minimumCardPickup(self, cards: List[int]) -> int:
        last = {}
        ans = inf
        for i, x in enumerate(cards):
            if x in last:
                ans = min(ans, i - last[x] + 1)
            last[x] = i
        return -1 if ans == inf else ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They want you to notice that every valid answer is bounded by two equal values, not by an arbitrary expandable window.
question_mark
They expect the shortest segment for a repeated value to come from its most recent previous index, not from the first time it appeared.
question_mark
They are testing whether you can replace window simulation with a direct last-seen hash lookup on an array scan.

warning

常见陷阱

外企场景

error
Using the first occurrence of a value instead of the most recent one, which misses shorter spans like the later 4-length window in [3,4,2,3,4,7].
error
Building a full sliding window with counts and shrink steps, which adds complexity without helping this exact duplicate-span problem.
error
Forgetting the +1 in j - i + 1, which undercounts the number of consecutive cards picked up.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the actual start and end indices of the shortest pickup instead of only its length.
arrow_right_alt
Find the longest consecutive pickup that still contains at least one matching pair.
arrow_right_alt
Process streaming card arrivals and report the current minimum duplicate span after each new card.

help

常见问题

外企场景

继续练习

#2461 长度为 K 子数组中的最大和 #2009 使数组连续的最少操作数 #2537 统计好子数组的数目