day5代码随想录-526互联

哈希表理论基础；242.有效的字母异位词349. 两个数组的交集202. 快乐数1. 两数之和

来源：代码随想录 (programmercarl.com)

6.2 哈希冲突 - Hello 算法 (hello-algo.com)

1哈希表理论基础

又称散列表

一般哈希表都是用来快速判断一个元素是否出现集合里。

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法

1.1哈希函数

通过某种哈希算法 hash() 计算得到哈希值。
将哈希值对桶数量（数组长度）capacity 取模，从而获取该 key 对应的数组索引 index 。

1.2哈希碰撞

2个输入元素都索引到了相同的输出位置，称为哈希碰撞

解决方法

扩容哈希表

「负载因子 load factor」是哈希表的一个重要概念，其定义为哈希表的元素数量除以桶数量，用于衡量哈希冲突的严重程度，也常作为哈希表扩容的触发条件。

改良哈希表数据结构，使得哈希表可以在出现哈希冲突时正常工作。
仅在必要时，即当哈希冲突比较严重时，才执行扩容操作。

1.2.1 链式地址

1.2.2 开放寻址

1. 线性探测

2. 平方探测

平方探测与线性探测类似，都是开放寻址的常见策略之一。当发生冲突时，平方探测不是简单地跳过一个固定的步数，而是跳过“探测次数的平方”的步数，即 1,4,9,… 步。

3. 多次哈希

顾名思义，多次哈希方法使用多个哈希函数f1(x)、f2(x)… 进行探测。

1.3 三种哈希算法的数据结构

1.3.1 数组

1.3.2 set（集合）

集合	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::set	红黑树	有序	否	否	O(log n)	O(log n)
std::multiset	红黑树	有序	是	否	O(logn)	O(logn)
std::unordered_set	哈希表	无序	否	否	O(1)	O(1)

红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

1.3.3 map（映射）

映射	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::map	红黑树	key有序	key不可重复	key不可修改	O(logn)	O(logn)
std::multimap	红黑树	key有序	key可重复	key不可修改	O(log n)	O(log n)
std::unordered_map	哈希表	key无序	key不可重复	key不可修改	O(1)	O(1)

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。

当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。

那么再来看一下map ，在map 是一个key value 的数据结构，map中，对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的。

2 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1: 输入: s = "anagram", t = "nagaram" 输出: true

示例 2: 输入: s = "rat", t = "car" 输出: false

说明: 你可以假设字符串只包含小写字母。

2.1 思路

暴力法：2层for循环

数组哈希表法：以空间换时间，定义一个26大小的数组，记录在字符串s中出现的字母次数，在字符串t中做减法，如果数组全为空，就说明是字母异位词。（包含完全相同的情况）

2.2 代码

/**
 * @file hash_2.h
 * @author nrt (1454250786@qq.com)
 * @brief 有效的字母异位词
 * @version 0.1
 * @date 2023-12-04
 * 
 * @copyright Copyright (c) 2023
 * 
 */
#include <iostream>

using namespace std;
class Solution {
public:
    bool isAnagram(string s, string t){
        int A[26] = {0};
        //字符串s计字符出现次数。做加法
        for(int i =0; i < s.size(); i++){

            A[s[i] - 'a'] ++;
        }
        //字符串t计字符出现次数，做减法
        for(int j = 0; j < t.size(); j++){
            A[t[j] - 'a'] --;
        }
        //不为零，就说明有字符不同
        for(int x = 0; x < 26 ; x++){
            if(A[x] != 0){
                return false;
            }

            return true;
        }
        
    }

};

3 两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。

3.1 思路

主要要学会使用一种哈希数据结构：unordered_set，这个数据结构可以解决很多类似的问题。

3.2 unordered_set

无序集合(unordered_set)是一种使用哈希表实现的无序关联容器，其中键被哈希到哈希表的索引位置，因此插入操作总是随机的。

无序集合上的所有操作在平均情况下都具有常数时间复杂度O(1)，但在最坏情况下，时间复杂度可以达到线性时间O(n)，这取决于内部使用的哈希函数，但实际上它们表现非常出色，通常提供常数时间的查找操作。

3.3 代码

/**
 * @file hash_3.h
 * @author nrt (1454250786@qq.com)
 * @brief 3 两个数组的交集
 *          给定两个数组，编写一个函数来计算它们的交集。
 *          学会使用一种哈希数据结构：unordered_set
 * @version 0.1
 * @date 2023-12-04
 *
 * @copyright Copyright (c) 2023
 *
 */
#include <iostream>
#include <vector>
#include <unordered_set>


using namespace std;
class Solution{
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set;
        //数组1的头到尾
        unordered_set<int> nums_set(nums1.begin(), nums1.end());
        for(int num : nums2){
            if(nums_set.find(num) != nums_set.end()){
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());

    }



};

4.快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 True ；不是，则返回 False 。

4.1 思路

判断sum是否重复出现就可以使用unordered_set。

这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false，否则一直找到sum为1为止。

4.2 代码

/**
 * @file hash_4.h
 * @author nrt (1454250786@qq.com)
 * @brief 快乐数
 * @version 0.1
 * @date 2023-12-04
 * 
 * @copyright Copyright (c) 2023
 * 
 */
#include<iostream>
#include<unordered_set>

using namespace std;

class Solution {
public:
    // 取数值各个位上的单数之和
    int getSum(int n){
        int sum = 0;
        while (n)
        {
            sum = (n%10) * (n%10);
            n = n/10;
        }
    }
    bool isHappy(int n) {
        unordered_set<int> result_set;
        while(1){
            int sum = getSum(n);
            if(sum == 1){
                return true;
            }

            if (result_set.find(sum) != result_set.end()) {
                return false;
            } else {
                result_set.insert(sum);
            }
            n = sum;
        }
    }

};

5. 两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

5.1 思路

本题，我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。

5.2 unordered_map

C++总结(7)：STL无序容器之unordered_set、unordered_map、unordered_multiset、unordered_multimap详解-CSDN博客

5.3 代码

/**
 * @file hash_5.h
 * @author nrt (1454250786@qq.com)
 * @brief 两数之和
 * @version 0.1
 * @date 2023-12-04
 * 
 * @copyright Copyright (c) 2023
 * 
 */
#include<iostream>
#include<unordered_map>
#include<vector>

using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
            unordered_map<int, int> map;
            for(int i = 0; i < nums.size(); i++){
                auto iter = map.find(target - nums[i]);
                if(iter != map.end()){
                    return {iter->second, i};//iter->second
                }
                map.insert(pair<int,int>(nums[i], i));//pair
            }

            return {};

    }
};

总结：

需要学习C++的STL。对STL无序容器之unordered_set、unordered_map不熟悉。

代码复现不熟练。