Medium

题目描述

给你一个整数数组 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^5
  • 0 <= cards[i] <= 10^6

解题思路

这道题要求找到包含一对相同值卡牌的最短连续子数组长度。

核心思路： 当我们遇到一个值时，如果之前见过相同的值，那么从上次出现位置到当前位置的区间就包含了一对匹配卡牌。我们要找的是所有这样区间中长度最小的。

算法步骤：

  1. 使用哈希表记录每个卡牌值最后一次出现的位置
  2. 遍历数组，对于每个位置的卡牌值：
    • 如果该值之前出现过，计算当前位置与上次出现位置的距离+1（即子数组长度）
    • 更新最小长度
    • 更新该值在哈希表中的最新位置
  3. 如果找到了匹配的卡牌对，返回最小长度；否则返回-1

时间复杂度： O(n)，只需遍历一次数组 空间复杂度： O(k)，k为不同卡牌值的数量，最坏情况下为O(n)

这种方法比暴力枚举所有连续子数组更高效，避免了O(n³)的复杂度。

代码实现

class Solution {
public:
    int minimumCardPickup(vector<int>& cards) {
        unordered_map<int, int> lastIndex;
        int minLen = INT_MAX;
        
        for (int i = 0; i < cards.size(); i++) {
            if (lastIndex.find(cards[i]) != lastIndex.end()) {
                minLen = min(minLen, i - lastIndex[cards[i]] + 1);
            }
            lastIndex[cards[i]] = i;
        }
        
        return minLen == INT_MAX ? -1 : minLen;
    }
};

class Solution:
    def minimumCardPickup(self, cards: List[int]) -> int:
        last_index = {}
        min_len = float('inf')
        
        for i, card in enumerate(cards):
            if card in last_index:
                min_len = min(min_len, i - last_index[card] + 1)
            last_index[card] = i
        
        return min_len if min_len != float('inf') else -1

public class Solution {
    public int MinimumCardPickup(int[] cards) {
        Dictionary<int, int> lastIndex = new Dictionary<int, int>();
        int minLen = int.MaxValue;
        
        for (int i = 0; i < cards.Length; i++) {
            if (lastIndex.ContainsKey(cards[i])) {
                minLen = Math.Min(minLen, i - lastIndex[cards[i]] + 1);
            }
            lastIndex[cards[i]] = i;
        }
        
        return minLen == int.MaxValue ? -1 : minLen;
    }
}

var minimumCardPickup = function(cards) {
    const lastIndex = new Map();
    let minDistance = Infinity;
    
    for (let i = 0; i < cards.length; i++) {
        if (lastIndex.has(cards[i])) {
            minDistance = Math.min(minDistance, i - lastIndex.get(cards[i]) + 1);
        }
        lastIndex.set(cards[i], i);
    }
    
    return minDistance === Infinity ? -1 : minDistance;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需遍历一次数组，哈希表操作为O(1)
空间复杂度O(k)k为不同卡牌值的数量，最坏情况O(n)

相关题目