代码随想录第6天 | ●哈希表理论基础●242.有效的字母异位词●349. 两个数组的交集●202. 快乐数●1. 两数之和

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

思路：

1.ASCII和哈希函数，存入数组，比较数组相等否
2.首先选择数据结构，题目只有小写字母，ASCII连续，选用数组，一个字符串遍历，在哈希数组中存入字母出现频率，第二个字符串遍历，做减法。（不需要记ASCII，直接减字母，编译器自己算）
时间复杂度: O(n)
空间复杂度: O(1)

坑：

无

补充：

哈希表理论基础

1. 哈希表是hash table 又叫散列表， 多用于快速判断某意思元素是否在集合里。（数组是一个哈希表。）
2. 哈希函数hash function把 实际的目标 映射到 哈希表上。
3. 哈希碰撞（冲突） 实际目标映射到了相同索引下标的位置。解决方法：
   ①拉链法：冲突的元素 存储在链表中
   ②线性探测法：要保证tableSize 大于dataSize，冲突的元素 存储在冲突位置往后的空位上。
   常见的哈希结构
4. 数组
5. set（集合）
6. map（映射）
   set和map的底层实现及优劣表

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

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

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

思路：

1. 类似上题，使用数组，根据元素的数值，存入数组对应下标中 但如果数值很大，映射到数组下标就不合适。
2. 该题去重，则选择unordered_set
   时间复杂度: O(n + m) m 是最后要把 set转成vector
   空间复杂度: O(n)

坑：

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.size()<nums2.size()){
            nums1.swap(nums2);
        }
        unordered_set<int> hash_set(nums1.begin(),nums1.end());
        unordered_set<int> result_set;
       for(int num: nums2){
            if(hash_set.find(num)!=hash_set.end()){
                result_set.insert(num);
                 //在集合hash_set中使用find函数查找num，找到返回一个指向该元素的正向迭代器，反之，返回一个类似end（）的迭代器
                 //找到则将该元素存入结果集合result_set中
            }
       }
        return vector<int>(result_set.begin(),result_set.end());
        //因为函数返回类型是vector 所以转换一下类型
    }
};

补充：

set集合
C++ STL unordered_set容器

范围for循环

范围循环：
for (类型 element : myVector) {
    std::cout << element << " ";
}

题目：202.快乐数

思路：

对n取余存入unordered_set 然后判断和是否为1，题目说可能无限循环，不知怎么判断

1. 无限循环是sum会重复出现 ,所以将每次循环的sum存入sums_set, 查找是否存在。
   2.看leetcode题解：双指针

坑：

1.数位分离，求平方和，可以简单的while和sum，不用多一步将个个数位上的值存入nums_set
2. % 是整数取余，/ 是除号

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> sums_set;
        int sum = 0;
        while (sum != 1) {
            sum=0;  //错误，sum 没有更新为0；
            while (n ) {// 错误 while的循环判断条件 不是n/10，这样会少判断元素
                sum+=(n%10)*(n%10);
                n = n / 10;
            }
            if(sums_set.find(sum)!=sums_set.end()){
                return false;
            }else{
                sums_set.insert(sum);
            }
            n=sum;
        }
        return true;
    }
};

题目：1.两数之和

思路：

1. 暴力法，枚举数组中的每一个数 x，寻找数组中是否存在 target - x。遍历，与目标值作差，在数组中寻找差值
2. 升级，方法一时间复杂度较高在于，target-1的遍历， 所以将遍历过的值x和下标保存到一个集合，之后遍历的时候来询问这个集合 ，target-x是否遍历过。因为需要保存值和下标 所以选用map，因为无序，-》unordered_map

坑：

补充：

今日总结