企业官网建设流程全解析

做力扣周赛碰到 3159 这道题时，我的第一反应是"这不就是个计数题嘛"，但真正提交之后才发现，读题不清的人远比我预想的多。题目本身不复杂，核心就一句话：给定目标元素 x，queries 里每个数字代表"第几次出现"，让你返回对应的数组下标，查不到就给 -1。整个过程就是"扫描一次、存位置、按查询查表"，时间复杂度 O(n+m)。这道题特别适合刚入门刷题的人用来建立"预处理换查询速度"的思维，也适合想在周赛里稳定拿分的老手快速热身。

1. 题目到底在问什么：需求拆解与常见误读

1.1 核心需求解析：queries 是次数不是下标

力扣 3159 的完整描述是：给你一个整数数组 nums、一个整数数组 queries 和一个整数 x，对 queries 中的每一个元素 q，找出 x 在 nums 中第 q 次出现时的下标，如果出现次数不足 q 次，就返回 -1。最终返回一个和 queries 等长的数组 answer，answer[i] 对应 queries[i] 的查询结果。

这里有一个特别容易混淆的点：queries 数组里的元素不是"下标"，而是"出现次数"。也就是说，queries[i] = 2 不是在问"下标 2 这个位置是什么"，而是在问"x 第二次出现在数组的哪个位置"。搞清楚这个语义，题目就解了一半，后面所有实现都是在围绕这个定义转。

1.2 一个例子把题目翻译明白

直接看例子。nums = [1, 3, 1, 7]，queries = [1, 3, 2, 4]，x = 1。x 是 1，nums 中 1 出现的位置分别是下标 0 和下标 2，那么：

• queries[0] = 1，问第 1 次出现的下标，结果是 0
• queries[1] = 3，问第 3 次出现的下标，总共才出现 2 次，结果是 -1
• queries[2] = 2，问第 2 次出现的下标，结果是 2
• queries[3] = 4，问第 4 次出现的下标，结果是 -1

最终答案就是 [0, -1, 2, -1]。

这个过程跟"查字典页码"很像：查一个字在第几页，先翻到索引页定位，而不是从第一页开始逐页找。先建立索引，之后每次查询都只需要翻索引，这就是本题解法的核心思路。

1.3 三种典型的读题错误

我在讨论区看到过几种很典型的误读。第一种是把 queries 里的值当成数组下标，直接去访问 nums，结果输出一堆莫名其妙的数字；第二种是忘了 x 是固定的，以为每个查询都要重新指定一个目标元素；第三种是把题目要求的"数组下标"理解成"第几次出现"，最后返回的是次数而不是位置。这些错误本质上都是读题时跳过了"q 表示第 q 次出现"这个关键定义。

实际上，这道题在周赛里处于比较靠前的位置，难度设计就是送分题。但正因为简单，反而容易因为粗心丢分。我的建议是拿到题先花 30 秒把输入输出语义写出来，再动手写代码，别急着提交。

2. 解题思路推导：为什么预处理一次就够了

2.1 暴力解法的时间账

最直白的想法是：对 queries 里的每一个 q，从头到尾遍历一遍 nums，数到第 q 个 x 时记录下标。这个方案实现起来非常快，几行就写完了，但性能很差。假设 nums 长度是 n，queries 长度是 m，最坏情况下每个查询都要完整扫描数组，总操作次数就是 n 乘 m。当 n 和 m 都达到 10 的 5 次方级别时，就是 10 的 10 次方次操作，任何评测环境都扛不住。

用生活化的例子说：这就好比去图书馆查一本书的借阅记录，每来一个读者问"第几次借给了谁"，管理员就把整本登记簿从头翻一遍。明明可以第一次就把所有借阅记录抄下来贴在墙上，后续查询直接抬头看墙。这个类比虽然简单，但"重复扫描"到底浪费在哪里，一目了然。

2.2 位置表预处理的核心思想

正确做法是处理 queries 之前，先遍历一次 nums，把所有等于 x 的下标按顺序存进一个列表 positions。具体步骤：

1. 初始化一个空列表 positions
2. 从左到右遍历 nums，设当前下标为 i，如果 nums[i] == x，就把 i 追加到 positions
3. 遍历结束后，positions[j] 就表示 x 第 j+1 次出现的下标

之后处理 queries 就变成了单纯的查表：对于 queries[i] = q，如果 q 大于 positions 的长度，说明出现次数不足，记 -1；否则答案就是 positions[q-1]。

这里为什么减 1？因为 positions 是 0 起始的，第 1 次出现存在 positions[0]，第 q 次出现自然存在 positions[q-1]。这个转换公式我建议直接写在注释里，后面会说到，它是整道题最容易写错的地方。

2.3 复杂度分析与最优性说明

预处理阶段只遍历一次 nums，时间复杂度 O(n)；查询阶段遍历一次 queries，每个查询是 O(1) 的列表访问，时间复杂度 O(m)。总体时间 O(n+m)。额外空间只用于存储 x 的出现位置，最坏情况下 x 每次都出现，空间 O(n)。

为什么说这是本题的最优解？因为任一查询本质上是"已知出现次数求位置"，回答任意一个这样的问题，至少需要知道 x 的出现位置序列，而构建这个序列本身就需要 O(n) 时间。你不可能在不读完整个数组的情况下得到完整的位置信息，所以时间复杂度的下限就是 O(n+m)。

这个"一次预处理、换取后续所有查询 O(1)"的思路，是算法里非常经典的"空间换时间"套路，也是后面延伸讨论的核心。

3. 三种语言实现与关键代码解读

3.1 Python 版：最贴近思路的写法

class Solution: def occurrencesOfElement(self, nums: List[int], queries: List[int], x: int) -> List[int]: pos = [] for i, v in enumerate(nums): if v == x: pos.append(i) ans = [] for q in queries: if q >= 1 and q <= len(pos): ans.append(pos[q - 1]) else: ans.append(-1) return ans

enumerate 同时拿到下标和值，判断 v == x 时把下标存进 pos，这是 Python 里最自然的写法。查询阶段注意两点：一是 q >= 1 的判断，二是 q <= len(pos) 的判断。第二个判断很容易被忽略，因为如果 q 恰好等于 len(pos)，说明 x 恰好出现了这么多次，最后一个位置 pos[len(pos)-1] 是合法答案，所以条件是小于等于而不是小于。

有人可能觉得 q >= 1 是多余的，题目约束里可能不会出现 0 或负数。但从防御性编程的角度看，这个条件成本几乎为零，却能避免 Python 里 q = -1 时 pos[-2] 这种"语义错误但不会崩溃"的诡异结果。我建议保留。

3.2 C++ 版：小心无符号比较的坑

class Solution { public: vector<int> occurrencesOfElement(vector<int>& nums, vector<int>& queries, int x) { vector<int> pos; for (int i = 0; i < (int)nums.size(); ++i) { if (nums[i] == x) { pos.push_back(i); } } vector<int> ans; ans.reserve(queries.size()); for (int q : queries) { if (q >= 1 && q <= (int)pos.size()) { ans.push_back(pos[q - 1]); } else { ans.push_back(-1); } } return ans; } };

C++ 版本有两个细节值得说。第一个是 reserve 预分配，pos 和 ans 的规模上限大致可估，提前 reserve 能避免多次扩容带来的拷贝开销。这道题数据量不大，效果不明显，但养成习惯是好事。

第二个是类型转换问题。pos.size() 返回的是 size_t 无符号类型，而 q 是 int。如果直接写 q <= pos.size()，当 q 是负数时，它会被隐式转换成很大的无符号数，比较结果可能出乎意料；当 q 是 0 时，0 <= size 恒成立，下一步访问 pos[-1] 直接越界崩溃。所以保险写法是同时判断 q >= 1，并且把 pos.size() 转成 int 再比较，让所有逻辑都在有符号整数域内进行，行为完全可控。

3.3 Java 版：集合与数组的选择

class Solution { public int[] occurrencesOfElement(int[] nums, int[] queries, int x) { List<Integer> pos = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { if (nums[i] == x) { pos.add(i); } } int[] ans = new int[queries.length]; for (int i = 0; i < queries.length; i++) { int q = queries[i]; if (q >= 1 && q <= pos.size()) { ans[i] = pos.get(q - 1); } else { ans[i] = -1; } } return ans; } }

Java 版用 ArrayList 存位置，get 是 O(1) 的，放心用。如果你追求极致性能，可以换成一个 int[] 数组手动维护 count，因为 x 出现次数的上限就是 nums.length，直接开等长数组即可，省去 Integer 装箱的开销。在数据量极大的极端场景下有微小优势，日常刷题用 ArrayList 就够了。

3.4 一个可选的提前终止优化

前面的实现都是完整扫描完 nums 再处理查询。其实可以先找到 queries 里的最大值 max_q，然后在扫描 nums 时，一旦 pos 的长度达到 max_q 就提前 break。因为 queries 最多只需要知道第 max_q 次出现的位置，后面的位置信息根本用不上。

max_q = max(queries) pos = [] for i, v in enumerate(nums): if v == x: pos.append(i) if len(pos) == max_q: break

这个优化在 x 频繁出现、而 queries 只问很小的次数时能把扫描提前截断。最坏情况下 x 几乎不出现，依然要遍历完整个数组，时间复杂度还是 O(n)，但它确实能省掉一部分无意义的工作。C++ 和 Java 里同样可以这么做，思路一致。

4. 边界条件清单与测试用例设计

4.1 容易翻车的 8 类边界场景

我习惯把所有边界情况列成清单，逐个排查才算把题吃透：

第 3 行和第 4 行尤其值得说。题目约束里可能保证了 queries[i] >= 1，那我为什么还要写防御性判断？因为面试官很可能追问一句"如果 queries 里出现 0 怎么办"，而且实际工程中数据永远比你想象的脏。数组越界这种事，一次就能让人长记性。

4.2 测试用例对照表

我在本地验证时常用下面这几组用例，覆盖了大多数分支：

最后一个用例特别能检验代码质量。不防御的话，Python 版会把 -1 当成倒数第二个位置，输出一个错误的"位置"；C++ 版甚至可能直接越界。拿这个用例一跑，问题立刻现形。

4.3 提交前的五步自查

写完代码我会按这个顺序过一遍：

1. queries 里的值是否全部按"第 q 次出现"处理，而不是当成数组下标
2. 返回的 answer 是否与 queries 等长
3. 是否处理了 q 为 0 或负数的情况
4. 是否处理了 q 大于出现总次数的情况
5. 位置信息是否用的是 0-based 数组下标

这五条都过了，基本不会在判题上出问题。

5. 常见问题与排查技巧实录

5.1 索引越界报错的根源与修复

典型报错是 C++ 的越界检查或者 Java 的 ArrayIndexOutOfBoundsException。如果代码里只写了 q <= pos.size() 而漏了 q >= 1，那么 q = 0 时一定会走进取 pos[q-1] 也就是 pos[-1] 的分支。原因是 0 对任何非负长度都成立，但"第 0 次出现"这个概念根本不存在。修复就是前面代码里的写法：条件加上 q >= 1。

这个坑我印象很深。以前写类似的处理第 k 次出现的代码，总觉得"题目不会给 0"，结果有一次在隐藏用例里翻了车。从那以后，只要是"第 k 次出现"这类问题，我都会顺手把 k >= 1 写上去。多写一个条件几乎不花成本，却能挡住一类事故。

5.2 输出偏移一位的隐蔽 bug

另一个非常常见的问题是忘记减 1，把第 1 次出现的下标写成了 pos[q] 而不是 pos[q-1]。这种 bug 隐蔽在：如果 x 第一次出现在下标 0，那 pos[0] 恰好等于 0，pos[1] 等于 1，很多用例不用减 1 也能碰巧输出正确答案，直到隐藏用例才暴露。

排查办法是构造一个 x 第一次出现位置不是 0 的用例，比如 x 第一次出现在下标 5，query = 1 就应该返回 5。如果用 pos[1] 的写法返回了第二个位置，问题立刻曝光。本质上这是 0-based 存储和 1-based 查询之间的转换问题，我建议在代码注释里直接写明：pos[第 k 次 - 1] = 下标。

5.3 超时场景的定位方法

提交显示超时，基本可以断定代码里还在对每个 query 重复扫描 nums。排查办法很简单，看主循环结构：如果 queries 的循环里还套了一层遍历 nums 的循环，那就是 O(n*m)，必须改成预处理。还有一小部分超时是因为查询阶段用了高复杂度操作，比如在列表上频繁调用 index 方法或者每次动态拼接字符串，这些都要避免。

5.4 分阶段调试的小技巧

刷题时我习惯在本地搭一套最简单的测试环境。Python 直接用 assert 断言跑用例，C++ 写一个 main 函数调用 Solution 里的方法。一旦某个用例挂了，就先打印预处理之后的 pos 列表，确认位置信息对不对，再单独检查查表逻辑。这种"分阶段定位"比盯着整段代码发呆高效得多，尤其是定位偏移一位这种逻辑错误时，打印中间结果几乎是最高效的手段。

6. 题型总结与个人刷题体会

6.1 "多次查询"题型的通用套路

力扣 3159 属于一个很大的题型：多次查询数组中的位置、次数、区间信息。这类题有一个共同的解题框架：能预处理就预处理，把查询阶段的时间压到 O(1) 或 O(log n)。举几个例子：

• 查询某个数在区间内出现的次数：预处理前缀和数组
• 查询第 k 个满足某条件的元素位置：预处理候选位置列表再配合二分
• 查询某个值第 k 次出现的下标：就是本题，预处理位置列表直接索引

以后遇到任何"给定多次查询"的题目，都可以先套一遍这个框架，大概率能找到正确的解法方向。

6.2 从本题看离线查询思想

本题其实是"离线查询"思想的最简单版本：先把所有信息收集好，再统一回答所有问题。进阶版的离线查询包括按查询排序后统一扫描、莫队算法等，本质都是同一个内核。理解了这一点，再看那些难题就不会觉得它们凭空出现了，无非是把"预处理"这一步做得更复杂而已。

6.3 为什么简单题也要亲手写一遍

最后说点实在的。像 3159 这种简单题，很多人觉得"看一遍解析就会了"就直接跳过，但我还是建议亲手写一遍，并且故意把边界条件写错几次，看看评测系统会给出什么反馈。这种对错误的体感记忆，比看十遍正确代码都管用。

还有一个小心得：把这类"第 k 次出现"的问题和找第 k 大、第 k 小的题目放在一起对比着做，你会发现它们都在反复训练"排名"和"位置"之间转换的敏感度。刷题刷到后面，真正拉开差距的不是背了多少模板，而是这种敏感度。我自己是吃了几次偏移一位的亏之后，才彻底把"次数转下标要先减一"这个动作刻进肌肉记忆里的，希望这篇文章能帮你少走这段弯路。