图 1：本文封面，环形手串与滑动窗口示意。
先说明属性：这是一篇笔试真题复盘，题目出自本地历史笔试资料整理，与任何公司的当前招聘无关。题意：一条 n 颗珠子串成的环形手串，每颗珠子可以无色，也可以涂若干种颜色，颜色共 c 种。要求是：任意一种颜色，在任意连续的 m 颗珠子里至多出现一次。问有多少种颜色不满足要求——也就是存在某个连续 m 颗的窗口，让该颜色出现至少两次。数据范围：n ≤ 10⁴，m ≤ 10³，c ≤ 50。
一句话思路：断环为链——把前 m−1 颗复制接到尾部，再用长度 m 的滑动窗口扫一遍，窗口内某颜色计数到 2 就把它标记为违规，答案是去重后的违规颜色种数。
为什么难在「环形」。 如果手串是直线，一个普通滑动窗口就解决了；环形的麻烦在首尾相接：最后一颗和第一颗相邻，跨端点的窗口（比如最后 2 颗加第 1 颗）在直线扫描里根本没有位置。处理环形结构有个通用套路——断环为链：把前 m−1 颗复制一份接到链尾，所有跨端点的窗口就都有处可放。窗口从链头滑到原链尾，恰好 n 个位置，不重不漏。
窗口里维护什么。 一个长度 c+1 的计数数组：珠子进入窗口时，它身上的每种颜色计数加一，离开窗口时减一；某种颜色计数加到 2，就进违规集合。注意题目问的是「多少种颜色违规」而不是「违规多少次」，所以用集合去重，同一颜色被抓到多次只算一次。每颗珠子进出窗口各一次，时间 O(n × 每颗平均颜色数），额外空间 O(c)，对照数据范围非常宽裕。
用代码实现并跑四组用例（Node.js 22.15.0，node bracelet.js）：
function countBadColors(n, m, c, beads) {
const k = Math.min(m, n); // 窗口长度不超过环长
const ext = beads.concat(beads.slice(0, k - 1)); // 尾部拼接前 k-1 颗
const cnt = new Array(c + 1).fill(0);
const bad = new Set();
const add = (i) => {
for (const color of ext[i]) {
cnt[color]++;
if (cnt[color] >= 2) bad.add(color); // 窗口内同色第二次出现
}
};
const remove = (i) => { for (const color of ext[i]) cnt[color]--; };
for (let i = 0; i < k; i++) add(i); // 初始窗口 [0, k)
for (let i = 1; i < n; i++) { remove(i - 1); add(i + k - 1); }
return bad.size;
}
实测输出：
样例一（官方样例 n=5 m=2）违规颜色数 = 2 （期望 2）
样例二（八珠手串 m=3）违规颜色数 = 1 （期望 1）
样例三（无违规）违规颜色数 = 0 （期望 0）
样例四（跨端点违规）违规颜色数 = 1 （期望 1）
样例一的违规颜色是 2 号和 3 号：2 号出现在第 1、3、4 颗，第 3 与第 4 颗相邻落进同一个窗口；3 号出现在第 1、3、5 颗，第 5 颗的下一颗就是环上的第 1 颗——这个违规只有跨端点窗口才抓得住，正是断环为链的意义。样例四同理：颜色只出现在首尾两颗，直线扫描必然漏报。
图 2：断环为链与滑动窗口计数的四步流程。
等价视角：按颜色看间距。 滑动窗口之外还有一种理解方式：把每种颜色的出现位置按环序排好，相邻两次出现（含首尾环绕）的珠子距离如果小于 m，这两颗就能被某个 m 窗口同时装下，该颜色违规。两种写法判据等价，窗口版不用排序、一趟扫完，更适合在笔试时限里写对。
边界与失分点。 三个容易栽的地方。第一，漏掉跨端点窗口——只扫直线窗口，答案偏小；第二，把「多少种颜色」做成「多少次违规」，忘了去重；第三，off-by-one：长度 m 的窗口要覆盖跨端点情形，需要复制的恰好是前 m−1 颗，多复制会重复计数、少复制会漏。另一个值得主动交代的边界是 m ≥ n：窗口不短于整圈，意味着任何出现两次的颜色都违规，实现里把窗口长度收到 min(m, n) 即可。
面试现场的答题结构。 先复述题意并确认「问的是违规颜色种数」，再指出环形是唯一难点、给出断环为链，然后写出窗口加计数数组的主流程并主动报复杂度，最后把 m=1、m ≥ n、同色去重这几个边界点出来。你在笔试里遇到过环形结构的题吗？当时是怎么处理的？欢迎分享。