利用哈希表(hash)解决问题

Hash表被称作哈希表，也叫做散列表。哈希表是一种比较特殊的数据结构，它遵循函数映射的思想，以Key: Value的方式存储数据。哈希表最大的特点是可以快速定位到要查找的数据，查询的时间复杂度接近O(1)。

接下来我们来分析几道可以利用哈希表的思想解决的题目。 第一题：宝石与石头问题 题目是这样说的：

给定字符串 J 代表石头中宝石的类型，和字符串 S 代表你拥有的石头。 S 中每个字符 代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。J 中的字母不重 复，J 和 S 中的所有字符都是字母。字母区分大小写，因此"a"和"A"是不同类型的石头。 示例 1: 输入: J = “aA”, S = “aAAbbbb” 输出: 3 示例 2: 输入: J = “z”, S = “ZZ” 输出: 0 注意: S 和 J 最多含有 50 个字母。 J 中的字符不重复

这道题目我想到了三种解决办法，一种是利用双层循环遍历；另一种是利用字符查找函数进行宝石的查找；第三种是实现一个哈希表，利用哈希表记录宝石的种类，然后再遍历一遍统计宝石的数量。

首先我们用循环来解决这道题目：时间复杂度为O(n^2)，空间复杂度为O(1)。

int numJewelsInStones(char* J, char* S)
{
          
   
	int num = 0;//统计宝石的数量
	for (int i = 0; J[i] != ; i++)//宝石
	{
          
   
		for (int j = 0; S[j] != ; j++)//自己的石头
		{
          
   
			if (S[j] == J[i])//如果自己的石头和宝石中的相同
			{
          
   
				num++;//宝石的数量++
			}
		}
	}
	return num;
}

我们还可以利用字符的查找函数进行宝石的查找：时间复杂度为O(n)，空间复杂度为O(1)。

int numJewelsInStones(char* J, char* S)
{
          
   
	int num = 0;//统计宝石的数量
	for (int i = 0; S[i] != ; i++)
	{
          
   
		if (strchr(J, S[i]))//在J中依次查找S中的每个字符
		{
          
   
			num++;//若找到了则宝石的数量++
		}
	}
	return num;
}

第三种方法的代码如下：时间复杂度为O(n)，空间复杂度为O(1)。由于只开辟了一个大小为128字节的空间，所以说空间复杂度为O(1)。

int numJewelsInStones(char* J, char* S)
{
          
   
	int num = 0;
	char arr[128] = {
          
    0 };
	for (int i = 0; J[i] != ; i++)
	{
          
   
		arr[J[i]] = 1;//将宝石记录下来
	}
	for (int i = 0; S[i] != ; i++)
	{
          
   
		if (arr[S[i]] == 1)//如果石头里面有标记为1的说明就是宝石
		{
          
   
			num++;
		}
	}
	return num;
}

如下图所示代码分析：

接着我们再来看一道可以利用哈希表解决的题目，如下：

写一个函数返回bool值，来判断给定的字符串A和B（假设都是小写字母），是否是B中的字符都存在于A中，如果是返回true，否则返回false

这道题目和上面那个宝石与石头的思想一模一样，同样的也可以利用三种方法去解决它，分别为双层循环，字符传查找函数以及哈希表，在这里我们是写利用哈希表解决的代码：

bool checkString(const char* A, const char* B)
{
          
   
	char arr[128] = {
          
    0 };
	while (*A != )
	{
          
   
		arr[*A++] = 1;
	}
	while (*B != )
	{
          
   
		if (arr[*B++] != 1)
		{
          
   
			return false;
		}
	}
	return true;
}