找位置：哈希映射与顺序输出的字符串处理技巧-北京尧图网络

刷题时遇到编号 3610 的“找位置”第一反应是“这题名字取得也太朴素了”。等真正动手做了才发现它几乎是字符串处理里最典型的一类题给你一串字符找出出现次数超过一次的字符并且把每个字符出现过的所有位置都输出出来。题目本身不复杂但它把“哈希映射”“顺序稳定输出”“格式化打印”这三个基础功揉在一起对刚刷 Online Judge 的新手来说很容易在小细节上翻车。我见过不少人逻辑明明写对了但提交上去就是 Wrong Answer原因往往不是算法错了而是输出顺序、逗号位置、重复输出字符这类细节没处理好。这篇文章就把这题从头拆到脚从题意理解到代码实现再到我实际试出来的各种坑一条一条讲清楚。如果你正准备笔试、刚开始刷 OJ 题目或者想练一下“字符位置映射”这种典型思路这篇应该能帮你省下不少时间。看完之后你不仅能拿下这一题还能把同款思路用到日志分析、文本去重、数据清洗这些实际场景里。1. 题目到底想让你做什么1.1 先用人话翻译一遍题面题目名“找位置”输入通常是一行字符串不含空格长度不会太长。需要你统计每个字符在字符串中出现的所有下标位置然后只输出那些出现次数大于 1 的字符以及它们的全部下标。举个很经典的例子输入 abcaabb预期输出长这样a:0,3,4 b:1,5,6这里的下标从 0 开始计数。字符 a 分别出现在位置 0、3、4字符 b 出现在位置 1、5、6。字符 c 只在位置 2 出现过一次所以它不参与输出。很多新手看到这个例子会觉得简单但请注意几个隐含条件输出的字符顺序必须按照该字符第一次在字符串中出现的顺序排列。上面例子里 a 第一次出现在位置 0b 第一次出现在位置 1所以先输出 a 再输出 b。如果你用“字符的字典序”来排序得到的结果可能是“a:0,3,4 换行 b:1,5,6”这个例子碰巧没错但如果输入变成 “bcaabc”正确答案应该是 b 在前因为 b 第一次出现在位置 0而不是让 a 按字母序排在前面。这一条不仔细读题的人最容易忽略。1.2 输出格式的隐藏考点这类题在 OJ 里的输出格式要求通常非常严格差一个空格、差一个换行、多了个逗号都会直接报 Presentation Error 或 Wrong Answer。以“找位置”为例标准格式是一行一个字符字符和后面的位置列表用英文冒号分隔位置之间用英文逗号分隔行尾没有多余空格。我见过有人写成这样a : 0, 3, 4多加了空格看起来更美观但在 OJ 看来这就是错的。还有人在最后一个位置后面加了逗号比如a:0,3,4,这也是典型的格式错误。另外还有个容易踩的点如果输入里有多个重复字符每个字符只能输出一次。你可以理解为每个“字符”是一行而不是每次出现都输出一行。这个规则看似自然但在代码实现时如果不加一个“是否已输出”的标记很容易造成同一个字符被重复打印好几遍。2. 从读题到建模核心是“字符到位置列表”的映射2.1 用哈希表还是数组其实是一回事先说我拿到这题的第一反应需要一个容器把每个字符映射到它出现过的所有位置。这个映射关系是核心后面的所有逻辑都围绕它展开。在绝大多数语言里最简单的做法就是用哈希表key 是字符value 是一个列表。遍历字符串每遇到一个字符就把当前下标追加到这个字符对应的列表里。遍历完成后再对哈希表做一次筛选只留下长度大于 1 的列表。但很多 C/C 选手会更偏向用数组因为字符的 ASCII 编码范围非常有限。普通英文字母、数字加上常见符号总共也就 128 个扩展 ASCII 也就 256。直接开一个vectorint pos[128]或者vectorvectorint pos(128)连哈希函数都省了用字符的 ASCII 码直接做下标。这样做的本质就是用 ASCII 码做“算术哈希”碰撞概率为零。在处理纯 ASCII 输入时这是最快的方案时间复杂度 O(n)空间复杂度也是 O(128 n)基本可以忽略不计。2.2 为什么不能只用一个“出现次数”数组如果只记录每个字符出现了多少次确实能知道哪些字符是重复的但拿不到它们出现的位置也就没法输出。所以这道题的关键不是计数而是“边计数边存位置”。有种偷懒的思路是先跑一遍统计出现次数然后再跑一遍遇到出现次数大于 1 的字符当场输出位置。这样也能做但需要两次遍历而且如果你第二次遍历时没有额外记录就会重复输出同一个字符。更干净的做法是第一遍直接存好所有位置输出阶段利用一个标记数组来去重。从建模角度来说这个映射关系也可以延伸到很多场景。比如你想统计一篇文章里哪些单词出现过多次并输出它们所在的行号或者分析日志里同一个 IP 在哪些时间戳出现过这本质都是同一套“某个值 → 一组位置”的模型。3. 完整实现与关键代码说明3.1 C 版本一次遍历解决问题我把 C 版本的实现直接放在这里代码不长但每一行的作用都不小。#include iostream #include string #include vector using namespace std; int main() { string s; while (cin s) { vectorvectorint pos(128); for (int i 0; i (int)s.size(); i) { pos[(unsigned char)s[i]].push_back(i); } // 标记某个字符是否已经输出过 bool printed[128] {false}; for (int i 0; i (int)s.size(); i) { int c (unsigned char)s[i]; if (printed[c]) continue; if (pos[c].size() 1) { printed[c] true; cout (char)c :; for (int j 0; j (int)pos[c].size(); j) { if (j 0) cout ,; cout pos[c][j]; } cout endl; } } } return 0; }代码思路分三步第一遍遍历字符串把每个字符的下标都追加到对应的pos列表里然后从头到尾再遍历字符串利用printed标记保证每个字符只处理一次一旦发现某个字符出现次数大于 1立刻按顺序输出它的所有位置。这里有个细节值得说一下为什么输出阶段不直接遍历pos数组而是再遍历一次原始字符串因为直接遍历pos数组是按 ASCII 码从小到大的顺序不是按字符在原始字符串中第一次出现的顺序。用原始字符串作为“顺序基准”才能保证输出顺序符合题目要求。3.2 为什么循环里要写while (cin s)很多 OJ 题目会有多组测试数据输入文件里可能有很多行字符串每一行都要单独处理并输出答案。如果不写while (cin s)只处理一行就退出遇到多组数据就会少输出很多结果最后就会导致 Wrong Answer。这种“持续读到文件结束”的写法是所有 OJ 多组测试题的标准姿势。用 Python 的话对应的写法是import sys for line in sys.stdin: s line.strip() if not s: continue pos {} for idx, ch in enumerate(s): pos.setdefault(ch, []).append(idx) printed set() for idx, ch in enumerate(s): if ch in printed: continue if len(pos[ch]) 1: printed.add(ch) print(ch : ,.join(map(str, pos[ch])))Python 里用字典天然适合这个场景setdefault可以避免手动判断 key 是否存在。这里的printed用集合去重和 C 里的bool数组是一个作用。3.3 逗号输出的通用技巧输出位置列表时最容易出现的错误就是多出一个结尾逗号比如a:0,3,4,。我习惯用一个判断if (j 0) cout ,也就是除了第一个元素之外其余的每个元素前面都补一个逗号。这种方式比“每次先判断是不是最后一个如果是就不输出逗号”要清晰得多也基本不会写错。在 Python 里更简单直接用,.join(...)就好。如果你用 Java可以参考StringJoiner也可以手动用同样的判断模式。很多字符串拼接类题目其实都适合这个套路不光是这道题。只要是“多个元素用同一种符号分隔”的输出需求用“除第一个外其余前面补分隔符”的方式比“拼完之后去掉末尾分隔符”更不容易出错。3.4 关于字符范围的补充我上面开数组时直接写了 128这个大小对普通 ASCII 字符足够。但如果你输入的字符串可能包含中文或 UTF-8 编码的多字节字符这就不是最优方案了。比如用 C 的cin s读入中文字符串实际按字节读入一个中文会变成好几个字节直接用s[i]去当数组下标会出现负数或越界。解决方式有两个一是规定题目输入就是纯 ASCII这种情况最常见二是改用unordered_mapchar, vectorint或者mapchar, vectorint让哈希表来处理更复杂的字符类型。具体选哪种看题目的输入范围描述。如果题目没有明确说明我建议直接用哈希表实现这样更稳。4. 我刷这类“找位置”题踩过的坑4.1 重复输出同一个字符这是我最早犯的错误。第一次写的时候我在统计完所有位置之后直接遍历整个pos数组看到哪个列表长度大于 1 就输出。本来以为这样没问题后来发现输入里如果同一个字符连续出现很多次输出也会重复好几遍。原因很有意思我当时不是遍历pos而是在第二次遍历原始字符串时遇到“出现次数大于 1 的字符”就直接输出但没有标记“这个字符已经处理过”所以同一个字符每出现一次就会输出一次。加了printed标记之后才算是真正把问题解决。这个坑在真实工程里也有对应版本做数据去重时如果只判断“这个值是否满足条件”但忘记记录“这个值是否已处理”遇到重复数据就会重复处理。对应的解决方案就是多维护一个“已完成集合”。4.2 排序顺序和字典序混淆我上面已经提到输出顺序必须按字符在原始字符串中首次出现的顺序。有些新手会觉得“反正输出所有重复字符用 map 按字母序输出不也挺整齐”但这不是题目要求的顺序。我们再看一个反例。输入是cbacba正确答案是c:0,3 b:1,4 a:2,5因为字符 c 第一次出现在位置 0是最早出现的重复字符。但如果直接用mapchar, vectorint遍历得到的顺序会变成a:2,5 b:1,4 c:0,3这在很多 OJ 上都会被判定为 Wrong Answer。要想避免这个问题最稳妥的方案就是“以原始字符串的遍历顺序为基准来决定输出顺序”。也就是第二次遍历原始字符串而不是直接遍历字符表。4.3 空串和单字符输入如果输入是一行空字符串程序应该什么都不输出直接结束。如果输入只有一个字符比如a这个字符只出现一次也不满足输出条件所以同样什么都不要输出。很多新手在本地测试的时候没测过这种边界输入提交上去才发现问题。实际上处理空串的代码很简单如果s为空直接跳过。我的 C 代码里没有显式判断空串因为for循环不会进入printed数组也会正常初始化输出自然为空。但如果你在代码里额外做了些别的操作比如先输出一个表头那就要小心了。我在本地调试时习惯把边界用例列成一张表逐一检查。输入期望输出实际该注意的点空串无输出循环不进入即可单个字符无输出出现次数不大于 1全部相同的字符a:0,1,2,...列表很长检查逗号大小写混合大小写视为不同字符A和a是两个 key带数字和符号按 ASCII 处理下标从 0 开始4.4 下标到底从 0 开始还是从 1 开始这个也容易翻车。题目一般会说清楚下标从 0 开始但有些变体题会从 1 开始。如果你做完样例测试发现统一差了个 1别急着找算法问题先看看是不是下标基准错了。如果题目没有明确说明可以先按样例输出推断。比如样例abcaabb输出a:0,3,4说明是 0 基下标。如果输出了a:1,4,5那可能就是 1 基下标。判断错这个代码改起来只需要在push_back(i)时改成push_back(i 1)或者push_back(i)。5. 如何验证你的代码一定正确5.1 自测用例的设计思路刷题最忌讳的就是写完全部代码交给 OJ 判题自己完全不验证。我个人的习惯是至少准备四类测试数据。第一类是题目给的原始样例这能保证基本方向正确。第二类是简单到极致的边界输入比如空串和单个字符。第三类是顺序敏感的数据专门输入cbacba这种重复字符交织排列的情况用来验证输出顺序是否符合首次出现顺序。第四类是全部字符都一样的情况比如aaaa验证长列表的输出格式。这里重点说“顺序敏感”的数据。如果你能想到构造一个用例使“按字典序输出”和“按首次出现顺序输出”的结果不一样那么你的代码测试才能暴露这一类错误。这种反向思维在准备笔试时也很有用不要只做能通过的用例还要主动构造能暴露代码弱点的用例。5.2 复杂度的自我检查这个题的解法时间复杂度是 O(n)空间复杂度是 O(n)。如果你写的版本复杂度变成 O(n^2)说明可能有性能问题需要重新检查。为什么有些人会写出 O(n^2)一种常见操作是每次遇到一个字符就用一个循环从头到尾扫描一遍所有已记录的位置看这个字符是不是已经出现过相当于用一个数组模拟哈希表的功能。在数据量小的时候没感觉但字符串长度到十万级别就会超时。正确的做法是直接用哈希表或固定数组保存位置查询和追加都是 O(1) 平均复杂度。我还会额外估算一下空间使用情况。比如字符串长度为 10 万每个位置用 int 保存占 4 字节总共有 10 万个位置约 400 KB这个量级完全没问题。但如果你在循环里不小心复制了太多临时字符串空间和时间都可能飙升。5.3 本地编译和 OJ 提交的差异C 代码在本地编译通过不代表 OJ 上一定能通过。常见问题包括没有引入正确的头文件、使用了一些非标准扩展、或者变量名与系统函数冲突。以“找位置”这题来说最容易忽略的是把数组命名为data或者index在有些编译环境下可能没问题但为了稳妥起见我会尽量用不太会冲突的变量名比如posList、cnt、printed。如果你在本地用的是 Dev-C 或者 Code::Blocks建议把编译标准至少调到 C11。如果你跟我一样用命令行编译可以加一句g -stdc11 -O2 -Wall -o solution solution.cpp-Wall会显示所有警告-O2是 OJ 上常见的优化级别。加上这两个参数再跑一遍可以提前暴露不少隐形问题。6. 从“找位置”延伸出去的真实场景6.1 在文本处理中统计字符出现位置这道题的思路放到真实项目中最直接的应用就是文本处理。比如你想知道某个长文本里“error”这个单词出现在哪些行或者“TODO”在代码仓库的所有文件里出现在哪些位置本质上都是“某个 key 对应一组位置”的问题。区别在于真实场景里 key 可能是一个单词而不是单个字符位置可能是行号而不是下标。但核心的数据结构并没有变用哈希表把 key 映射到一个列表遍历数据时不断追加位置最后筛选长度大于 1 的列表。我做过一个小脚本用来扫日志文件里所有告警关键词出现的时间点。做法很简单把每一行日志按时间戳和关键词拆分构建一个关键词 - 时间列表的哈希表最后输出每个关键词出现的时间列表。全程没有用到复杂算法但解决实际问题的效率很高。6.2 数据清洗中的重复值定位另一个场景是数据清洗。假设你拿到一份 Excel 导出的名单里面有一些重复记录你想知道每条重复记录分别在哪些行。同样可以先遍历所有记录用“记录内容”作为 key记录行号到列表里最后只看长度大于 1 的 key。这个场景下需要注意一个额外问题如果记录内容很长直接作为哈希表的 key 比较占内存。实际项目中可以先对内容做一次哈希比如用简单的字符串哈希或摘要算法得到一个较短的指纹再用指纹作为 key。这和“找位置”这道题里的 ASCII 码下标思路一脉相承只是哈希函数从“直接取 ASCII 码”变成了更复杂的映射。6.3 笔试题里的同类变体很多公司笔试会把这个题稍微改一改再拿出来考。比如把字符改成单词输入一段英文文章输出所有出现次数大于 1 的单词以及它们出现的句子序号或者把位置改成二维坐标在地图格子里标记相同颜色块的位置。改来改去核心解法还是没有跳出“哈希映射顺序输出”的框架。你只要把“字符”换成任意可哈希的对象“位置”换成对应的索引或编号整个解题思路可以直接复用。我个人的体会是这类基础题真正考察的不是你背了多少高级算法而是你能否在简单场景里快速建模并且在输出格式这种细节上做到滴水不漏。笔试时间紧张很多人会在最后一个逗号、换行、重复输出上扣冤枉分。与其临场紧张不如平时就把这些边界条件想透形成肌肉记忆。最后再分享一个我自己的小习惯代码写完不要急着提交先从输入输出两个方向分别做一次心理检查。输入方向是“空输入、单字符输入、特殊字符输入”输出方向是“第一个字符、最后一个字符、整行格式、多组数据之间有没有多余空行”全部过一遍再提交基本能一次通过。

找位置：哈希映射与顺序输出的字符串处理技巧

相关推荐

IEEE会议LaTeX模板作者信息不显示？spconf.sty排查与修复指南

四旋翼姿态控制PID建模与Simulink仿真全流程解析

Claude Code本地调用链路搭建：从Codex协议网关到VS Code集成

更多资讯

DeepSeek Harness 客户端深度解析：本地执行 Agent 工作流与实操指南

基于LSTM-CNN混合模型的智能电表故障预测技术解析

智能微电网调度算法实战：从目标函数建模到滚动时域优化

Java旅游管理系统毕业设计部署全流程指南

基于Java的个人博客系统毕设：Spring Boot+MyBatis架构与部署答辩全攻略

SVM姿势检测实战：关键点特征工程与调参避坑指南

今日更新

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？