题解 | #奶牛排队问题#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param weights int整型一维数组
     * @param n int整型
     * @param k int整型
     * @return bool布尔型
     */
    public boolean checkDuplicate (int[] weights, int n, int k) {
        // write code here
        HashMap<Integer, ArrayList<Integer>> t = new HashMap<>();
        HashSet<Integer> cow = new HashSet<>();

        for (int i = 0; i < n; i++) {
            if (!t.containsKey(weights[i])) {
                t.put(weights[i], new ArrayList<Integer>());
            }
            t.get(weights[i]).add(i);
        }

        for (ArrayList<Integer> v : t.values()) {
            for (int i = 1; i < v.size(); i++) {
                if (v.get(i) - v.get(i - 1) <= k) {
                    return true;
                }
            }
        }

        return false;
    }
}

编程语言是Java。

这道题目考察的主要知识点是使用哈希表和集合来判断数组中是否存在重复元素，并且要求判断重复元素的索引之差是否小于等于k。

具体代码的文字解释如下：

• 在 checkDuplicate 方法中定义一个 HashMap<Integer, ArrayList<Integer>> t，用于存储每个元素在数组中的索引列表。
•  HashSet<Integer> cow 来记录已经访问过的元素，确保不重复判断相同的元素。
• 通过遍历数组 weights，对于每个元素，如果在 t 中不存在对应的键，则新建一个索引列表并将其加入到 t 中；如果键已经存在，则直接将当前索引加入到该列表中。
• 循环结束后，我们遍历 t 中的每个索引列表。对于每个索引列表，通过判断相邻两个索引之间的差值是否小于等于 k，来确定是否存在满足条件的重复元素。如果找到满足条件的重复元素，则返回 true，表示存在重复元素；否则返回 false，表示不存在重复元素。
• 在这个过程中，通过使用哈希表 t 和集合 cow，我们可以高效地判断数组中是否存在重复元素，并且只需要遍历一次数组。