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

🎯 问题描述（来源于LeetCode）

描述：
给你一个整数数组 cards，其中 cards[i] 表示第 i 张卡牌的值。
如果两张卡牌的值相同，则认为这一对卡牌是匹配的。
请你找出必须拿起的最小连续卡牌数目，使得其中包含一对匹配的卡牌。
如果无法找到匹配的一对卡牌，返回 -1。

说明：

这是一个哈希表结合贪心算法的问题。
核心逻辑是：对于每个数字，记录它最后一次出现的位置。
当再次遇到该数字时，计算当前位置与上次出现位置之间的距离，并更新最小距离。
通过一次遍历即可完成查找。
示例：
示例 1：

输入：cards = [3,4,2,3,4,7]
输出：4
解释：
- 拿起 [3,4,2,3] 包含一对匹配的 3，长度为 4。
- 拿起 [4,2,3,4] 包含一对匹配的 4，长度为 4。
- 最小长度为 4。

示例 2：

输入：cards = [1,0,5,3]
输出：-1
解释：
- 没有匹配的卡牌对。

💻 解题思路

思路1：哈希表记录最后出现位置

思路1：代码实现

class Solution:
    def minimumCardPickup(self, cards: List[int]) -> int:
        # 哈希表：键为卡牌值，值为该卡牌最后一次出现的索引
        count = defaultdict(int)
        # 初始化最小长度为一个大值（根据题目约束，最大长度为 10^5）
        ans = 10**5 + 1
        
        for i, num in enumerate(cards):
            # 如果当前卡牌值之前出现过
            if num in count:
                # 获取上次出现的位置
                left = count[num]
                # 计算当前连续卡牌数目：i - left + 1
                # 例如：[3,4,2,3]，left=0, i=3, 长度=3-0+1=4
                ans = min(ans, i - left + 1)
            
            # 更新当前卡牌值的最后出现位置
            count[num] = i
        
        # 如果没有找到匹配的卡牌对，返回 -1
        if ans == 10**5 + 1:
            return -1
        
        return ans

思路1：📊 性能分析

时间复杂度： $O(N)$ $O (N)$
- 其中 $N$ 是数组 cards 的长度。
- 我们只遍历数组一次，每次哈希表操作（查找、插入、更新）的平均时间复杂度都是 $O(1)$ 。
- 总时间复杂度为 $O(N)$ 。
空间复杂度： $O(N)$ $O (N)$
- 哈希表 count 在最坏情况下需要存储 $N$ 个键值对。

思考

贪心策略：
- 我们想要最小化连续卡牌数目，因此对于每个数字，我们只需要记录它最后一次出现的位置。
- 当再次遇到该数字时，与最后一次出现的位置配对，可以得到以当前位置结尾的最短连续子数组。
- 这种策略是贪心的，因为它总是选择最近的相同数字来最小化距离。
哈希表的作用：
- 哈希表用于记录每个数字最后一次出现的索引。
- 这样，当再次遇到该数字时，可以快速计算距离。
逻辑流程：
- 遍历每个卡牌 cards[i]。
- 检查当前卡牌值 num 是否在哈希表中：
  - 是：说明之前出现过。计算从上次出现位置 left 到当前位置 i 的连续卡牌数目 i - left + 1，并更新最小值 ans。
  - 否：说明第一次出现，无需计算。
- 更新哈希表中 num 的最后出现位置为 i。
距离计算：
- 连续卡牌数目 = 结束索引 - 开始索引 + 1。
- 例如，[3,4,2,3]，开始索引为 0，结束索引为 3，长度为 3 - 0 + 1 = 4。
边界情况：
- 数组长度为 1：无法配对，返回 -1。
- 所有数字都不同：无法配对，返回 -1。
- 所有数字都相同：最小长度为 2（相邻的两个相同数字）。

思路二：滑动窗口

思路二：代码实现

class Solution:
    def minimumCardPickup(self, cards: List[int]) -> int:
        # 哈希表：记录窗口内每个数字出现的次数
        count = defaultdict(int)
        # 初始化最小长度为一个大值
        ans = 10**5 + 1
        # 滑动窗口左边界
        left = 0
        
        # 右边界向右遍历
        for right, num in enumerate(cards):
            # 将当前数字加入窗口
            count[num] += 1
            
            # 如果当前数字在窗口内出现次数大于1，说明有重复（匹配）
            while count[num] > 1:
                # 更新最小长度：当前窗口大小
                ans = min(ans, right - left + 1)
                
                # 尝试收缩左边界
                count[cards[left]] -= 1
                left += 1
                
        # 如果没有找到匹配的卡牌对，返回 -1
        if ans == 10**5 + 1:
            return -1
            
        return ans

思路二：📊 性能分析

时间复杂度： $O(N)$ $O (N)$
- 其中 $N$ 是数组 cards 的长度。
- 虽然代码中有嵌套循环（while），但每个元素最多被 right 指针访问一次，被 left 指针访问一次。
- 因此，总的时间复杂度是线性的 $O(N)$ 。
空间复杂度： $O(N)$ $O (N)$
- 哈希表 count 在最坏情况下需要存储 $N$ 个键值对。

思考

滑动窗口原理：
- 我们维护一个窗口 [left, right]。
- right 指针不断向右移动，将新元素加入窗口。
- 一旦窗口内某个数字的数量超过 1（即 count[num] > 1），说明找到了一个包含匹配对的子数组。
- 此时，我们需要尝试缩小窗口（移动 left 指针），看看能否在保持“包含匹配对”的前提下获得更短的长度。
收缩逻辑：
- 当 count[num] > 1 时，说明当前 num 是重复的。
- 我们记录当前窗口长度 right - left + 1 并更新 ans。
- 然后，我们将 cards[left] 的计数减 1，并将 left 右移。
与思路一的对比：
- 思路一（哈希表记录位置）：直接通过数学计算 i - last_pos + 1 得到距离，更加直观且常数时间更优。
- 思路二（滑动窗口）：是一种通用的处理“最小子数组”问题的方法。虽然在这里也能达到 $O(N)$ ，但逻辑相对复杂一些，因为它需要维护窗口的收缩。
边界情况：
- 数组长度为 1：count 最大为 1，while 循环不执行，返回 -1。
- 所有数字都不同：同上，返回 -1。
- 所有数字都相同：right 移动到 1 时，count 变为 2，进入 while，计算长度 2，收缩直到 count 变回 1。正确。