做算法题的时候我有个习惯先把“看起来最直白的解法”在脑子里过一遍再追问一句“如果数据量放大一百倍这个解法还顶得住吗”。力扣3159这道题——查询数组中元素出现的位置恰恰就是用来回答这个问题的经典例子。题目本身很短核心就一件事给你一个数组再给一堆查询每个查询问你某个元素第一次出现在数组的哪个下标。不用哈希表也能做但如果你真用暴力去扫面对10的5次方级别的数据就会明显感觉到吃力。这篇文章我想从这道题出发把“查询优化”这条线完整拆开从题目解析到哈希表预处理从首次出现扩展到第k次出现再聊到这类映射思想在真实工程里的落地方式。这道题适合谁看如果你正在准备算法面试刚入门数据结构和哈希表或者在工作中写过类似“查配置、查索引、查位置”的小工具那后面的内容可以帮你直接把思路落成代码。即使你已经AC过这道题也可以重点看第三节和第五节那里讲的是从一道题演变成一类题的思路以及算法和工程之间那层容易被忽略的对应关系。1. 题目核心解析与解题思路1.1 题目到底在问什么力扣3159的题面简化之后是这样一个场景给定一个下标从0开始的整数数组nums再给一个查询数组queriesqueries里的每个元素都是要查询的目标值。对于每个查询需要返回该目标值在nums中第一次出现的位置也就是下标如果目标值在nums中压根不存在就返回-1。举个具体的例子假设nums [1, 3, 1, 7]queries [1, 3, 2, 4]那答案就是[0, 1, -1, -1]。原因很简单数字1在nums中第一次出现在下标0数字3第一次出现在下标1数字2和4在nums中完全没有所以返回-1。很多人在第一次读题时会忽略两个细节。第一个细节是“第一次出现”这意味着同一个值可能在数组里重复出现多次我们不能返回任意一次的位置必须是最早的那个。第二个细节是下标从0开始计数所以下标0是合法答案它和“返回-1表示不存在”之间有着本质区别。这两个细节看起来不起眼但恰恰是后面最容易出bug的地方我在第四节会专门展开。1.2 暴力解法为什么撑不住拿到这道题直觉解法自然是双重循环外层遍历每个查询内层遍历整个nums数组找到第一个和目标值相等的元素就记录下标遍历完还没找到就记为-1。伪代码大概长这样def brute_force(nums, queries): res [] for q in queries: pos -1 for i, x in enumerate(nums): if x q: pos i break res.append(pos) return res如果只看代码这个做法完全正确测试样例也都能过。但一旦把数据规模放大问题就暴露了。假设nums长度为nqueries长度为q最坏情况下每个查询都要把整个数组完整扫一遍总的比较次数就是n乘以q。当n和q都达到10的5次方量级总操作数就是10的10次方这在普通判题环境下是几秒甚至几十秒都跑不完的负担超时几乎是必然的。暴力法的本质问题是它重复遍历了同一份数据。你把nums从头到尾扫了q遍但仔细想想扫第一遍的时候就已经能获得所有元素的位置信息了后面的q减1遍完全是在做重复劳动。我经常用找超市商品来打比方暴力法是每一个顾客来了你都在整个超市里带他转一圈找货而聪明的做法是第一天就整理一张“商品到货架位置”的对照表之后顾客来了直接查表一步到位。1.3 思路转变一次扫描多次查询既然暴力法的痛点是重复遍历那优化方向自然就是“把多次遍历变成一次遍历用空间把查询时间换下来”。具体做法是先扫一遍nums用一个容器记录每个元素第一次出现的下标。扫描完成后容器里就有了所有需要的信息。接下来的每个查询都不再需要回到nums里去找只需要在容器里做一次读取。这个读取操作平均只需要O(1)的时间和数组有多大基本无关。这就是典型的“预处理 查询”两步走模式。预处理阶段我们把数据从“原始数组”转换成了“索引结构”转换的成本是O(n)查询阶段每个问题都变成O(1)的查表操作整体复杂度从O(n乘以q)降到了O(n加q)。用一个朴素的比喻你花十几分钟整理了一份索引卡之后千百次查询都靠它这笔买卖非常划算。这种“空间换时间”的思路在算法题里叫预处理在工程里有一个更熟悉的词——建索引。数据库为什么查得快不是因为它会魔法而是因为它提前把索引结构放在那里了。理解了这一点你就理解了这道题真正想考的东西。2. 哈希表方案核心实现与复杂度剖析2.1 为什么选择哈希表确定了“预计算”的思路之后下一个问题是用什么容器来存放“元素值到下标的映射”这里的关键在于nums里的元素值是任意的整数范围可能是0到100也可能是负数甚至可能大到10的9次方。我们不能预知它的取值边界所以需要一个能动态存储任意整数key的映射结构。哈希表Map就是最自然的选择。哈希表的核心原理是把key通过哈希函数转换成一个桶的位置然后在桶里存放value。理想情况下不同key均匀分布到不同桶中读写的平均时间复杂度都是O(1)。Python里的dict、Java里的HashMap、C里的unordered_map都属于这类结构。如果你接触过哈希表的底层实现可能会担心哈希冲突导致性能退化。这个担心在工程上是存在的但刷题时基本可以放心主流语言内建的哈希表都有完善的扩容和冲突处理机制加上题目的数据是静态给出的不会故意构造对抗性输入所以平均O(1)的复杂度在力扣的数据范围内是稳定成立的。2.2 三种主语言的核心实现Python版本def occurrencesOfElement(nums, queries): first_pos {} for i, x in enumerate(nums): if x not in first_pos: first_pos[x] i return [first_pos.get(q, -1) for q in queries]Java版本public int[] occurrencesOfElement(int[] nums, int[] queries) { MapInteger, Integer firstPos new HashMap(); for (int i 0; i nums.length; i) { firstPos.putIfAbsent(nums[i], i); } int[] ans new int[queries.length]; for (int i 0; i queries.length; i) { ans[i] firstPos.getOrDefault(queries[i], -1); } return ans; }C版本vectorint occurrencesOfElement(vectorint nums, vectorint queries) { unordered_mapint, int firstPos; for (int i 0; i nums.size(); i) { if (!firstPos.count(nums[i])) { firstPos[nums[i]] i; } } vectorint ans; ans.reserve(queries.size()); for (int q : queries) { auto it firstPos.find(q); ans.push_back(it firstPos.end() ? -1 : it-second); } return ans; }三种语言的思路完全一致差别只体现在API上。注意Java的putIfAbsent和C的count判断目的都是相同的当元素重复出现时保留第一次记录的下标不被后面的重复项覆盖。Python的写法里if x not in first_pos同样是在做这件事。2.3 时间复杂度与空间复杂度验证先看时间。预处理阶段需要完整遍历nums长度是n所以是O(n)。查询阶段每个queries里的元素都执行一次哈希表的读操作平均O(1)queries长度为q所以查询阶段是O(q)。总复杂度O(n q)。再看不使用哈希表的暴力法O(n * q)。当n和q都是10的5次方时两者差了十万八千里。这就是为什么这道题的数据范围一旦拉满哈希表方案几乎是唯一合理选择。空间方面哈希表中最多存储nums里不同元素的个数极端情况下所有元素都不同空间就是O(n)。在实际编码中我用过一个对比表来帮助自己评估方案简单来说就是方案预处理时间单次查询时间总时间复杂度空间复杂度暴力遍历无O(n)O(n * q)O(1)哈希表预处理O(n)O(1)O(n q)O(n)数组映射预处理O(n)O(1)O(n q)O(值域范围)从这个表可以清楚看到哈希表和数组映射本质是同一类方案区别只在于空间用量。2.4 边界情况什么时候可以用数组替代哈希表有的同学可能会想到一个优化如果nums里的元素值域是连续且范围较小的直接用数组当下标映射表查询比哈希表更快因为数组访问是内存连续、缓存友好、绝对O(1)。这个想法在特定条件下是对的。例如nums里的值保证都在0到1000之间就可以开一个长度为1001的int数组初始化为-1然后做和哈希表完全相同的预处理。def occurrences_with_array(nums, queries, max_val): first [-1] * (max_val 1) for i, x in enumerate(nums): if first[x] -1: first[x] i return [first[q] if 0 q max_val else -1 for q in queries]但要注意使用数组有两个前提一是值域上限要可知且可控二是key不能是负数或超出上限的值。如果nums里的元素可能是负数或者值域跨度极大比如存在10的9次方级别的数字开数组就会造成巨大的空间浪费甚至直接越界报错。这时候哈希表就是唯一合理的选择。实操心得刷题时不要一上来就想着“用数组优化”先确认值域约束。力扣题面通常会给出nums元素的取值范围如果范围在10的6次方以内可以考虑数组超过这个量级或者存在负数直接用哈希表省心也不容易错。3. 从首次到第k次一道题带出一类题3.1 记录完整位置序列这道题考的是“第一次出现”但在真实面试和工程场景里更常见的需求其实是“某个元素第k次出现在哪里”或者“某个元素一共出现了多少次”。好消息是这些变体可以用同一个预处理思路解决只是存储的信息粒度不同。首次出现的做法是哈希表里存单个位置遇到重复元素就跳过。第k次出现的做法则是把哈希表的value从“单个int”升级成“一个位置列表”扫描nums的时候每遇到一个元素就在它对应的列表后面追加当前下标。扫描结束后每个元素都拥有了一个完整的、按照下标从小到大排列的位置序列。def kth_occurrence(nums, queries, k): positions {} for i, x in enumerate(nums): positions.setdefault(x, []).append(i) ans [] for q in queries: pos_list positions.get(q, []) ans.append(pos_list[k - 1] if len(pos_list) k else -1) return ans注意这里的k是“第几次”而不是下标所以取位置列表时要用k减1。这个细节特别容易写错我最早实现的时候就直接用了pos_list[k]结果边界一测就崩。提前把k减1写在注释里能帮助自己和读代码的人少踩坑。3.2 一类变体的对照总结同样一张表不同问题差别只在“怎么读写那个映射容器”问题需求预处理方式查询时的操作核心注意点第一次出现的位置不存在才写入直接读哈希表不能覆盖已有记录最后一次出现的位置每次都覆盖写入直接读哈希表最后写入的一定是最后一次出现的总次数每次出现都加1读计数用Counter计数即可第k次出现的位置追加到列表按下标读取注意k减1和边界判断区间[l, r]内出现次数追加到列表二分查找左右边界需要有序列表配合二分把这些变体放在一起看你会发现它们共享同一副骨架一次扫描构建索引结构查询阶段全部变成读取或简单的计算。刷题时遇到新题先识别它属于哪类映射需求代码基本可以套用。3.3 结合二分区间查询也很自然如果题目进一步升级要求你回答“元素x在区间[l, r]中出现了多少次”完全基于位置列表的方案依然可行。因为每个元素的位置列表天然是递增的所以只需要在列表里做两次二分查找一次找第一个大于等于l的位置一次找第一个大于r的位置两个下标的差值就是区间内的出现次数。import bisect def count_in_range(positions, x, l, r): pos positions.get(x, []) left bisect.bisect_left(pos, l) right bisect.bisect_right(pos, r) return right - left这里的核心洞察是位置列表本身就是一个有序数组有序数组最擅长的事情就是二分。当预处理阶段生成了有序索引后续的多种查询都可以在O(logn)的时间完成而不是扫描原始数组。从“首次出现”到“区间计数”变化的只是查询的姿势不变的是预处理构建索引的思想。3.4 离线处理的全局视角如果查询足够多而且查询之间不是独立的还有一个更高级的优化思路把queries里的值去重后再查或者把所有查询按元素值分组一次性处理。虽然哈希表方案本身已经很快但在极大数据量的工程场景里减少重复查询仍然有意义。我以前处理过一个日志分析任务日志文件里上亿行要统计几千个用户ID各自第一次出现的行号。当时就是把用户ID作为key行号作为value单趟扫描构建索引几千个查询全部O(1)返回内存占用也就几百兆。这其实就是力扣3159的工程放大版换了个数据规模换了个场景思路一模一样。4. 易错点、边界条件与调试实录4.1 下标0和-1的混淆这道题最常见的坑是把“下标0”和“不存在返回-1”搞混。下标0是合法答案表示目标元素在数组的起始位置就出现了-1才表示不存在。问题出在一些习惯性写法上比如有人用if (firstPos[q])来判断key是否存在在Python里等价于if first_pos.get(q):但当下标是0时这个条件会被判定为假于是0就被错误地换成了-1。如果你的代码里出现了“明明数组里第一个元素就是答案结果返回了-1”的情况八成就是这个问题。修法也很简单判断key是否存在要判断的是“key是否在字典里”而不是“value是否为真值”。Python里用if q not in first_posJava用containsKeyC用find。4.2 记录首次位置时被覆盖在预处理阶段如果代码写成for i, x in enumerate(nums): first_pos[x] i那遍历结束后哈希表里存的是每个元素最后一次出现的位置而不是第一次。题目要求首次出现时这个写法会直接错。我调试这类bug时有一个熟练技巧在纸上模拟一个小用例比如nums [1, 1, 1]queries [1]期望答案是0如果代码返回2那几乎可以断定是写入时少了“不存在才写入”的判断。记住这句口诀首次出现用“判断后写”最后一次出现才用“直接覆盖”。4.3 查询里出现重复值queries [1, 1, 1]这种输入不需要做任何特殊处理因为每次查询都是独立的哈希表读取读一万次结果都一样。但值得留意的是如果同一个元素查询次数特别多使用哈希表比使用扫描数组的收益更大。每次查询都是O(1)不会因为重复查询而增加额外负担。不要画蛇添足地尝试给queries去重那反而会增加代码复杂度。4.4 空数组与空查询的边界nums为空时哈希表是空的任何查询都返回-1代码天然成立。queries为空时答案应该是一个空数组千万别返回null。C里注意给ans预留容量或直接返回空vectorJava里new int[0]也是合法输出。4.5 值域极端时别误用数组假如nums里有负数或者极大整数使用定长数组会带来两个风险一是负数的下标访问直接越界二是为了覆盖一个极大值而开一个巨大的数组内存直接爆炸。判断标准很简单值域紧凑且非负才考虑数组否则一律哈希表。这也是我在2.4节反复强调的原因。4.6 一份易错点速查表易错点典型错误表现正确做法用value真值判断存在下标0被误判为不存在判断key是否在映射中预处理时直接覆盖返回最后一次位置不存在才写入第k次用错下标越界或取错位置用k-1访问列表数组映射未检查值域负数越界、超大内存先确认值域再选方案空查询返回null判题直接崩溃返回空数组注意提交前至少自己构造一个“目标元素在0号位”的用例和一个“目标元素不存在”的用例这两个用例能挡掉八成以上的隐藏错误。5. 映射预处理思想在真实工程中的落地5.1 配置服务中的键值映射真实系统里把一批配置数据一次性加载到哈希表里然后对外提供O(1)查询接口是最常见的工程应用。比如路由表、黑白名单、促销活动配置本质上都是“一个key对应一个value”启动时构建映射运行期只读查询。算法题里的预处理对应到工程就是服务启动时的加载阶段。这个阶段花掉的时间是可控的、一次性的换来的是整个运行期的高效响应。5.2 日志索引与首次访问定位我在实际项目中做过一个用户行为分析模块数据源是按天产出的行为日志每行记录是一个用户的一次操作。业务方经常问的问题是“某个新功能上线后用户的第一次使用发生在什么时间”如果直接扫描全量日志每查一个用户都要跑一遍几百万行的文件完全不可接受。实际做法和力扣3159几乎一一对应单趟扫描日志文件用用户ID做key第一次出现的行为时间做value构建一张“用户首次使用时间”的映射表。之后业务方的任何查询都是查表。整个预处理过程只需要几分钟但省去了后续成千上万次的全量扫描。你可以把数组里的下标理解成日志的行号把元素值理解成用户ID两者的算法结构完全一致。5.3 电商序列中的第k次行为分析推荐系统里有一个常见特征叫“商品在用户浏览序列中的位置信息”。比如想要知道某个商品是否是用户第3次浏览时加购的就需要在用户的行为序列中找到该商品的第3次出现位置。工程实现就是对这个用户的行为序列做一次遍历用商品ID做key位置下标列表做value然后查询第k次时直接按下标访问列表。这跟3.1节的kth_occurrence如出一辙。区别只在于算法题里的数组可能只有几千个元素而真实行为序列可能有上百万条记录算法题里只需要做一次查询工程里同一个key可能被反复询问。无论哪种情况“预处理一遍后续全部查表”都是最高效的策略。5.4 从刷题到工程三个值得内化的判断标准刷完这道题我建议你把这套思维沉淀成三个条件反射式的判断第一如果同一份数据会被多次查询就应该考虑预处理。第二如果查询频率远高于更新频率空间换时间几乎总是划算的。第三如果key的种类多、范围不稳定优先想到哈希表而不是数组。这三个判断在算法题里适用在写工具脚本、设计服务接口时同样适用。很多时候我们写出的代码慢不是因为CPU不行而是因为同样的数据被反复扫描而没人去建索引。力扣3159把一个很工程化的思想压缩成了半页代码这是它值得琢磨的地方。就我个人而言刷完这道题之后我在处理本地的“批量文件内容定位”这类脚本时都会下意识先问自己一句要不要建一份索引哪怕只是一个临时字典。这个习惯带来的性能收益往往比什么微优化都显著。如果你也准备把它用到真实场景建议先从小规模数据开始验证确认内存可接受再放大到全量数据这样最稳妥。