代码随想录 Day5 哈希表1 T242 相同字母的异序词 T349两个数组的交集 T202 快乐数 T1 两数之和（上）

本文详细解答和思路来自于:

代码随想录 (programmercarl.com)

前导知识 - 哈希表

定义:哈希表是根据关键码的值而直接进行访问的数据结构.所谓的关键码就是下标实际上数组就是一张哈希表.

那么哈希表有什么作用呢?哈希表可以以O(1)的性能迅速定位你要找的元素,相较于依次遍历提升了很多性能,比如说你在公司里要查找一个人是否在公司,在查询的时候通常只需通过索引就可以知道该人是否在公司里.

所以哈希表通常使用于在集合中查询某个元素是否存在.

这个时候将公司成员映射到哈希表上,这就用到了哈希函数 (Hash function).

哈希碰撞

一般我们要存入哈希表的元素大小是小于哈希表的大小了该怎么办?或者是哈希函数给两个元素计算的的索引下相同怎么办?

我们刚刚说过,哈希表就是一个数组,那么就算哈希函数计算的再均匀,也会有元素无家可归,

两个元素去争一块空间的情况我们就成为哈希碰撞.

下面是哈希碰撞的两种解决方式:

1.链表法

在哈希表大小大于要存入数组的元素或者小于数组的元素都可以使用

操作如下:

2.线性探测法

只有在哈希表大小大于要存入元素大小的时候可以使用. 简单来说就是在后面再找一个空位来存放,比如说小李和小王算得的哈希值都是1,这时候小李先填入,再填入小王的时候发现2的位置没有值,那么小王就可以填入二号值.

Leetcode T242 相同字母的异序词

题目链接:

242. 有效的字母异位词 - 力扣（LeetCode）

1.思路

这里由于哈希表的元素是有限的,我们可以采用数组来记录数据,首先创建一个26个元素的数组record来记录每个字母的出现次数,先遍历第一个字符串,将对应下标的数据++,然后遍历第二个字符串,将对应位置的数组元素数据--,最后进行一次遍历record数组,如果找到了不是0的元素,那么就返回false,全是0则返回ture.

2.代码

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] record = new int[26];
        //创建记录数组  
        for(int i = 0;i<s.length();i++)
        {
            //进行目标映射
            int tmp = (int)s.charAt(i)-'a';
            record[tmp]++;
        }
        for(int i = 0;i<t.length();i++)
        {
            int tmp = (int)t.charAt(i)-'a';
            record[tmp]--;
        }
        for(int j =0;j<record.length;j++)
        {
            if(record[j] != 0)
            {
                return false;
            }
        }
        return true;
    }
}

//如果我们想简洁一点,也可以使用增强for循环
for(int j:record)
{
    if(j != 0)
    {
        return false;
    }
}
return true;

Leetcode T349 两个数组的交集

题目链接:力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

1.题目思路

我们这里这道题一开始是没有给定nums1和num2的长度限制的,后来补上了限制,所以我们也可以用数组来实现,这里我们选择一个不同的方式来实现,我们知道HashSet是不存在重复数据的,所以这里我们使用HashSet来实现.

首先我们先判断两个数组是否为空数组,如果是空数组则可以直接返回.接着我们先创建两个HashSet:set1和set2,然后我们先遍历数组1,将数组1中的元素放入set1中,紧接着我们遍历第二个数组,如果数组中包含set1中的元素,就将该元素放入set2中,最后创建一个set2大小的数组用来返回.