南瑞java机考题目

### 南瑞 Java 机考题目解析

针对南瑞 Java 机考中的特定问题，考虑一道涉及算法处理的典型题目。该题目描述了一条由 n 个珠子组成的环形手串，每个珠子可能被涂上至多 c 种不同颜色[^2]。目标是从这 n 个珠子构成的手串中找到任意连续 m 个珠子内至少重复出现两次的颜色总数。

为了实现这个功能，下面提供了一个基于滑动窗口技术的方法来解决这个问题：

import java.util.*;

public class ColorCount {
    public static int findColors(int[] beads, int m) {
        Map<Integer, Integer> colorFrequency = new HashMap<>();
        Set<Integer> resultColors = new HashSet<>();

        // 初始化第一个窗口
        for (int i = 0; i < m; ++i) {
            colorFrequency.put(beads[i], colorFrequency.getOrDefault(beads[i], 0) + 1);
            if (colorFrequency.get(beads[i]) >= 2) {
                resultColors.add(beads[i]);
            }
        }

        // 滑动窗口遍历整个数组
        for (int i = m; i < beads.length + m - 1; ++i) {
            int currentIndex = i % beads.length;
            int outIndex = (currentIndex - m + beads.length) % beads.length;

            // 更新即将移除的颜色频率
            int outgoingColorFreq = colorFrequency.get(beads[outIndex]);
            if (outgoingColorFreq == 2) {
                resultColors.remove(beads[outIndex]);
            } else if (outgoingColorFreq > 2){
                resultColors.add(beads[outIndex]);
            }
            colorFrequency.put(beads[outIndex], outgoingColorFreq - 1);

            // 更新新加入的颜色频率
            colorFrequency.put(beads[currentIndex], colorFrequency.getOrDefault(beads[currentIndex], 0) + 1);
            if (colorFrequency.get(beads[currentIndex]) >= 2) {
                resultColors.add(beads[currentIndex]);
            }
        }

        return resultColors.size();
    }
}

上述代码实现了通过维护一个大小固定的滑动窗口，在每次移动过程中更新窗口内的颜色频度表，并据此判断哪些颜色达到了指定条件。最终返回符合条件的不同颜色的数量。