【Day06】哈希表Part01—哈希表理论基础、有效的字母异位词、两个数组的交集、快乐数、两数之和

今天是元旦，2024新的一年，祝大家在新的一年里开心顺遂，工作顺利、学业有成，做一些自己真正热爱的事情，今天主要是刷哈希表的一些题目。

今日任务

● 哈希表理论基础

● 242.有效的字母异位词

● 349. 两个数组的交集

● 202. 快乐数

● 1. 两数之和

一、哈希表理论基础

1.1 需要了解的知识点：

哈希表的内部实现原理、哈希函数、哈希碰撞，以及常见哈希表的区别，数组、set和map。

代码随想录：哈希表的基础知识点

1.2 什么时候用哈希法？

非常重要的一句话： 当遇到要快速判断一个元素是否出现在集合里面的时候，就要考虑哈希法。

• 哈希法也是牺牲了空间换取了时间：因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。如果在做面试题目的时候遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法！

题目二：242. 有效的字母异位词

参考链接：【代码随想录之有效字母异位词】

Leecode题目：242. 有效的字母异位词

很暴力的解法，采用两个数组实现：

class Solution {
public:
    bool isAnagram(string s, string t) {
        int s_count[26] = {0};
        int t_count[26] = {0};
        for(int i = 0; i < s.size(); i++){
            s_count[s[i] - 'a'] ++;
        }
        for(int j = 0; j < t.size(); j++){
            t_count[t[j] - 'a'] ++;
        }
        for(int k = 0; k < 26; k++){
            if(s_count[k] != t_count[k]){
                return false;
            }
        }
        return true;
    }
};

但也有非常巧妙的方法（只采用一个数组即可实现），一个++，一个–，判断最终的数组元素是否位0，只要有一个不为0，即不是字母异位词。

class Solution {
public:
    bool isAnagram(string s, string t) {
        int count[26] = {0};
        for(int i = 0; i < s.size(); i++){
            count[s[i] - 'a'] ++;
        }
        for(int j = 0; j < t.size(); j++){
            count[t[j] - 'a'] --;
        }
        for(int k = 0; k < 26; k++){
            if(count[k] != 0){
                return false;
            }
        }
        return true;
    }
};

题目二：349. 两个数组的交集

参考：【代码随想录之两个数组的交集】

Leetcode题目：349. 两个数组的交集

2.1 set的基础知识：

2.1.1 set的创建

unordered_set nums_set;

2.1.2 set的基本方法

2.1.3 set的遍历

// 遍历数组
for(auto i = nums_set.begin(); i!= nums_set.end(); i++){
    cout << *i << endl;
}

2.1.4 set的增删改查

find用法（集合.find(元素) ！= 集合.end()）：

for(int i = 0; i<nums2.size(); i++){
    if(nums_set.find(nums2[i]) != nums_set.end()){
        // 如果在数组中找到了
        result_set.insert(nums2[i]);    
    }
}

2.1.5 set数据结构的区别

2.2 vector数据结构

参考：C++数组（vector）常用操作总结

2.2.1 vector的初始化定义：

2.2.2 vector常见基础操作

2.2.3 使用迭代器可实现遍历、插入、删除操作

一个迭代器的范围由一对迭代器表示，分别为 begin 和 end。其中 begin 成员返回指向第一个元素的迭代器；end 成员返回容器最后一个元素的下一个位置（one past the end），也就是指向一个根本不存在的尾后位置，这样的迭代器没什么实际含义，仅是个标记而已，表示已经处理完了容器中的所有元素。所以 begin 和 end 表示的是一个左闭右开的区间 [ begin , end)

1、遍历:

auto it = a.begin();  // 返回一个迭代器类型，一般来说我们并不关心迭代器具体的数据类型
while(it != a.end())
{
    cout << *it << " ";
    it++;
}

2、在迭代器之前插入元素：

#include 
#include 
#include 
using namespace std;
 
int main(void)
{
    vector a{1, 2, 3, };
    auto it1 = a.begin();  // 返回一个迭代器类型，一般来说我们并不关心迭代器具体的数据类型
    auto it2 = a.insert((it1+1), {6, 7, 8});  // 利用迭代器在第二个元素之前插入数据
    cout << *it2 << endl;  // 返回的是新插入元素第一个元素的迭代器
    auto it = a.begin();  // 
    while(it != a.end())
    {
        cout << *it << " ";
        it++;
    }
    return 0;
}
// 输出结果 //
6
1 6 7 8 2 3

3、删除元素

4、查找元素

5、修改元素

6、元素排序：sort 与 reverse

2.3 回归题目

不选用数组哈希表解决的原因：

（1）由数组做哈希表的都是数组有固定长度的，但是此处的输入没有固定长度（默认元素无穷大）；

（2）哈希值比较少、特别分散、跨度非常大，使用数组就造成了空间的极大浪费。

新的思路（采用set数据结构解决）：

class Solution {
public:
    vector intersection(vector& nums1, vector& nums2) {
        // 寻找某一个元素是否出现在数组中，可以采用哈希方法实现
        unordered_set result_set;
        unordered_set nums_set;
        for(int i = 0; i < nums1.size(); i++){
            nums_set.insert(nums1[i]);
        }

        // 寻找nums2中的元素在nums1中是否出现过
        for(int i = 0; i<nums2.size(); i++){
            if(nums_set.find(nums2[i]) != nums_set.end()){
                // 如果在数组中找到了
                result_set.insert(nums2[i]);    
            }
        }

        // 遍历数组
        for(auto i = nums_set.begin(); i!= nums_set.end(); i++){
            cout << *i << endl;
        }
        return vector(result_set.begin(), result_set.end());

    }
};

最后的return如何理解？它其实就相当于是一种强转。

题目三： 202. 快乐数

Leetcode题目链接：【202. 快乐数】

题解分析：【代码随想录 之 快乐数分析】

思路：题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！

重点就在于这个求和上面，sum非常重要。

代码如下：

class Solution {
public:

    // 数字拆分求和
    int getSum(int num){
        int sum = 0, temp = 0;
        while(num){
            temp = num % 10;
            sum = sum + temp * temp;
            num = num / 10;
        }
        return sum;
    }

    bool isHappy(int n) {
        unordered_set num_set;
        int sum = getSum(n);
        num_set.insert(sum);
        while(true){
            sum = getSum(sum);
            if(sum == 1){
                return true;
            }
            if(num_set.find(sum) != num_set.end()){
                return false;
            }else{
                num_set.insert(sum);
            }
        }
        return true;
    }
};

题目四：1. 两数之和

参考：【代码随想录之两数之和】

Leetcode题目：两数之和

双循环的暴力解法：

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        vector num_value;
        // 直接双循环即可
        for(int i = 0; i < nums.size(); i++){
            for(int j = i + 1; j < nums.size(); j++){
                if(nums[i] + nums[j] == target){
                    cout << "i: " << i << " j: " << endl;
                    num_value.push_back(i);
                    num_value.push_back(j);
                    return num_value;
                }
            }
        }
        return num_value;     
    }
};