题解 | #奶牛排队问题#

考察的知识点：哈希；

解答方法分析：

1. 给定的奶牛队列 weights 是一个有序列表，即按照奶牛的编号顺序排列。
2. 判断是否存在体重相同且距离不超过 k 的两头奶牛。
3. 定义两个指针 left 和 right，初始时分别指向队列的第一个和第 k+1 个奶牛。
4. 对于每个针指向的奶牛，比较它们的体重，如果相等返回 true。如果不相等，则将两个指针同时向右移动位。
5. 重复步骤 4，直到 right 指针历完整个队列。
6. 如果步骤 5 结束后仍未找到体重相同的两头奶牛，则返回 false。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param weights int整型vector
     * @param n int整型
     * @param k int整型
     * @return bool布尔型
     */
    bool checkDuplicate(vector<int>& weights, int n, int k) {
        unordered_map<int, int> lastPosition;
        for (int i = 0; i < n; i++) {
            if (lastPosition.count(weights[i]) && i - lastPosition[weights[i]] <= k) {
                return true;
            }
            lastPosition[weights[i]] = i;
        }
        return false;
    }
};