刷题时遇到编号 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 第一次出现在位置 0，b 第一次出现在位置 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。直接开一个vector<int> pos[128]或者vector<vector<int>> 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) { vector<vector<int>> 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_map<char, vector<int>>或者map<char, vector<int>>，让哈希表来处理更复杂的字符类型。具体选哪种，看题目的输入范围描述。如果题目没有明确说明，我建议直接用哈希表实现，这样更稳。
4. 我刷这类“找位置”题踩过的坑
4.1 重复输出同一个字符
这是我最早犯的错误。第一次写的时候，我在统计完所有位置之后，直接遍历整个pos数组，看到哪个列表长度大于 1 就输出。本来以为这样没问题，后来发现输入里如果同一个字符连续出现很多次，输出也会重复好几遍。
原因很有意思：我当时不是遍历pos，而是在第二次遍历原始字符串时，遇到“出现次数大于 1 的字符”就直接输出，但没有标记“这个字符已经处理过”，所以同一个字符每出现一次就会输出一次。加了printed标记之后，才算是真正把问题解决。
这个坑在真实工程里也有对应版本：做数据去重时，如果只判断“这个值是否满足条件”，但忘记记录“这个值是否已处理”，遇到重复数据就会重复处理。对应的解决方案就是多维护一个“已完成集合”。
4.2 排序顺序和字典序混淆
我上面已经提到，输出顺序必须按字符在原始字符串中首次出现的顺序。有些新手会觉得“反正输出所有重复字符，用 map 按字母序输出不也挺整齐”，但这不是题目要求的顺序。
我们再看一个反例。输入是：
cbacba正确答案是：
c:0,3 b:1,4 a:2,5因为字符 c 第一次出现在位置 0，是最早出现的重复字符。但如果直接用map<char, vector<int>>遍历，得到的顺序会变成：
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，建议把编译标准至少调到 C++11。如果你跟我一样用命令行编译，可以加一句：
g++ -std=c++11 -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 的单词以及它们出现的句子序号；或者把位置改成二维坐标，在地图格子里标记相同颜色块的位置。
改来改去，核心解法还是没有跳出“哈希映射 + 顺序输出”的框架。你只要把“字符”换成任意可哈希的对象，“位置”换成对应的索引或编号，整个解题思路可以直接复用。
我个人的体会是，这类基础题真正考察的，不是你背了多少高级算法，而是你能否在简单场景里快速建模，并且在输出格式这种细节上做到滴水不漏。笔试时间紧张，很多人会在最后一个逗号、换行、重复输出上扣冤枉分。与其临场紧张，不如平时就把这些边界条件想透，形成肌肉记忆。
最后再分享一个我自己的小习惯：代码写完不要急着提交，先从输入输出两个方向分别做一次心理检查。输入方向是“空输入、单字符输入、特殊字符输入”，输出方向是“第一个字符、最后一个字符、整行格式、多组数据之间有没有多余空行”，全部过一遍再提交，基本能一次通过。
)
