数据结构：找出字符串中重复的字符（Finding Duplicates in a String）——使用哈希表

目录

第一步：最原始的思路

第二步：有没有办法记住某个字符是否出现过？

第三步：字符只有26个英文字母，那我可以建个数组！

🔍 什么是哈希表 （Hash Table）

第四步：统计每个字符出现的次数

 第五步：再遍历 count[] 数组，输出重复字符

---

问题定义

给定一个字符串 char str[] = "programming"，找出它里面所有重复出现过的字符，比如输出：

r
g
m

第一步：最原始的思路

我们什么都不知道，先按最直接的方式做：

方法 1：逐字符比较（双重循环）

• 对于字符串中的每个字符 str[i]

• 再从后面 str[j]（j = i+1 到末尾）检查是否有和 str[i] 相同的

• 如果发现重复，就记录它

for (int i = 0; str[i] != '\0'; i++) {for (int j = i + 1; str[j] != '\0'; j++) {if (str[i] == str[j]) {// 重复了}}
}

问题：太慢了！

• 对于长度为 n 的字符串，时间复杂度为 O(n²)

• 并且很难控制重复输出（比如 m 出现多次，我们会多次输出 m）

方法 2：排序 + 相邻比较

先排序，然后比较相邻元素是否重复：

sort(arr, arr + n);
for (int i = 1; i < n; i++) {if (arr[i] == arr[i - 1]) ...
}

• 提升效率到 O(n log n)

• 但是破坏原始顺序

• 需要排序，较重

第二步：有没有办法记住某个字符是否出现过？

现在我们开始用第一性推导来优化！

💡 你也许会问自己：

有没有一种方法，可以在 O(1) 时间内，判断一个元素是否出现过？ 

这就是我们逐渐走向哈希表的思想了，但我们还没到那一步。

“我能不能用一个数组，把每个字符是否出现过标记起来？”

这是“哈希表”要回答的问题。

第三步：字符只有26个英文字母，那我可以建个数组！

我们发现字符串是字母串，比如 "programming"

那么字符种类就只有 26 个小写英文字母 a~z，我们可以这样想：

int count[26] = {0};

表示：

• count[0] 表示字母 a 出现的次数

• count[1] 表示字母 b 出现的次数

• ...

• count[25] 表示字母 z

怎么得到字母对应的下标？

只需用：

int index = str[i] - 'a';

• 'a' - 'a' = 0

• 'c' - 'a' = 2

• 'z' - 'a' = 25

为什么我们需要一个“位置 → 值”的映射？

设想你有一本字典，你要查单词 apple 的定义。

你当然不可能从头到尾翻 10000 页去找，而是：

✅ 定位到它在第几页 → 一步翻过去 → 拿到它的定义

这个动作，我们可以抽象为：

key: "apple"  ——[某种转换函数]——→  index: 87  ——→ 存储/查找数据

我们刚刚找字符是否重复，本质也是一样：

int count[26];
int index = ch - 'a';

 其实就是：

字符 ch ——[计算偏移]——→ 数组索引 index ——→ 计数器 count[index]

这其实就是最基本的哈希表设计思想。 

🔍 什么是哈希表 （Hash Table）

哈希表是一种键-值对映射结构，它支持：

操作	时间复杂度
插入键值对	O(1) 平均
查找键对应值	O(1) 平均
删除键值对	O(1) 平均

哈希表的构造三要素

组成	第一性描述	示例
键（key）	你要查找的东西	'a'，"apple"，23
哈希函数	把“键”转成整数索引的方法	'a' - 'a' = 0
存储结构	存储键值的容器，一般是数组	count[26]，table[1000]

哈希函数是怎么做的？ 

最简单的方式：ASCII编码偏移

int index = ch - 'a'; // 适用于小写字母

更一般的：

int index = hash(key) % N;  // N 是表的大小

 哈希函数的目标：不同键 → 尽量分布到不同索引（避免冲突）

⚠️ 但哈希表有个不可避免的问题：冲突

什么是冲突？

两个不同的键，经过哈希函数映射到相同的索引

"abc" 和 "cba" → 都映射到 index = 7

哈希表如何解决冲突？

两种常见方式：

方法	思想
链式地址法（拉链法）	每个位置是一个链表，冲突的值插到链表中
开放地址法	如果发生冲突，向后找下一个空位

实际例子：count[26] 就是一个哈希表！

原始思考	抽象为哈希表设计
每个字母放在数组中	使用键：字符
用 str[i] - 'a' 得到索引	哈希函数
存次数	值：出现次数

所以你实际上已经构造了一个最小版本的哈希表！

---

第四步：统计每个字符出现的次数

我们用一遍遍历就能搞定：

for (int i = 0; str[i] != '\0'; i++) {int index = str[i] - 'a';count[index]++;
}

 第五步：再遍历 count[] 数组，输出重复字符

for (int i = 0; i < 26; i++) {if (count[i] > 1) {char c = 'a' + i;cout << c << " 出现了 " << count[i] << " 次" << endl;}
}

完整代码实现（小写英文字母版本）

#include <iostream>
using namespace std;void findDuplicates(char str[]) {int count[26] = {0}; // 初始化所有字母的次数为0// Step 1: 统计每个字符的出现次数for (int i = 0; str[i] != '\0'; i++) {int index = str[i] - 'a';if (index >= 0 && index < 26) {count[index]++;}}// Step 2: 输出出现次数 >1 的字符cout << "重复字符有：" << endl;for (int i = 0; i < 26; i++) {if (count[i] > 1) {char c = 'a' + i;cout << c << " 出现了 " << count[i] << " 次" << endl;}}
}int main() {char str[] = "programming";findDuplicates(str);return 0;
}