【Leetcode Daily】2260必须拿起的最小连续卡牌数

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个整型数组，找出其中子数组的最短长度，该子数组需满足至少内部有一个数字是出现两次及以上的。

思路分享

• 求子数组的最短长度属于不定长滑动窗口可以解决的范畴，因此可以参考 【Leetcode Daily】2904最短且字典序最小的美丽子字符串 的思路与解决方式。

• 接下来介绍一下枚举的思路，枚举就要比不定长滑动窗口实现上简单不少。就是昨天的 【Leetcode Daily】219存在重复元素II 的换了个语境，故不在此详细说明。

• 枚举的基本思路可以看 【Leetcode Daily】1两数之和。

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution {
public:
    int minimumCardPickup(vector<int>& cards) {
        // 用不定长滑动窗口求最小窗口长度比较好解
        // int res = INT_MAX;
        // unordered_map<int, int> rec;
        // int left = 0;
        // for (const int i : cards) {
        //     rec[i]++;
        //     // cout << "left:" << left << endl;
        //     while(rec[i] >= 2) {
        //         // cout << i << " " << cards[left] << endl;
        //         // cout << rec[i] << " " << rec[cards[left]] << endl;
        //         rec[cards[left]]--;
        //         if (rec[cards[left]] == 0) {
        //             rec.erase(cards[left]);
        //         }
        //         left++;
        //         int n = rec.size();
        //         res = min(res, n+1);
        //     }
        // }
        // return res==INT_MAX ? -1 : res;

        // 或者哈希表记录上一次的下标来枚举
        unordered_map<int, int> rec;
        int res = INT_MAX;
        for (int i = 0; i < cards.size(); i++) {
            int index = cards[i];
            if (rec.find(index)!=rec.end()) {
                res = min(res, i-rec[index]+1);
            }
            rec[index]=i;
        }
        return res==INT_MAX?-1:res;
    }
};