Day 6 | Leetcode 242, 349, 202, 1

链接

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

知识

哈希表理论基础

哈希表->哈希函数->哈希碰撞->拉链法/线性探测法->常见的三种哈希结构->set & map及如何选取->总结

哈希表

哈希表是根据关键码的值而直接进行访问的数据结构。举例：其实数组就是一张哈希表。哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素。

哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。

哈希函数

哈希函数：哈希函数，把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。如果hashCode得到的数值大于哈希表的大小了，也就是大于tableSize了，此时为了保证映射出来的索引数值都落在哈希表上，我们会在再次对数值做一个取模的操作，这样我们就保证了学生姓名一定可以映射到哈希表上了。

如果学生的数量大于哈希表的大小怎么办，此时就算哈希函数计算的再均匀，也避免不了会有几位学生的名字同时映射到哈希表同一个索引下标的位置。接下来哈希碰撞登场。

哈希碰撞

小李和小王都映射到了索引下标 1 的位置，这一现象叫做哈希碰撞。一般哈希碰撞有两种解决方法，拉链法和线性探测法。

拉链法/线性探测法

其实拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。使用线性探测法，一定要保证tableSize大于dataSize。我们需要依靠哈希表中的空位来解决碰撞问题。例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放冲突的数据了。

常见的三种哈希结构

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

数组
set （集合）
map(映射)

set & map及如何选取

std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

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

两个unordered都是哈希表实现的,其他四个都是红黑树实现的。三类set和三类map性质上是类似的。

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

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

虽然std::set、std::multiset 的底层实现是红黑树，不是哈希表，std::set、std::multiset 使用红黑树来索引和存储，不过给我们的使用方式，还是哈希法的使用方式，即key和value。所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法。 map也是一样的道理。

总结

总结一下，==当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法==。哈希法的查询速度很快：O(1)。

但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

如果在做面试题目的时候遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法！

题目

242.有效的字母异位词

将一个数组中的元素全部置为0：int hash[26] = {0};。实际上，直接写int hash[26]也可以，不给数组中的值赋值，数组中的值默认为0。
求字符串string s的长度，可以用s.size()，也可以用s.length()。
s[i] - 'a'：编译器会自动用ascii码进行计算，不需要手动将变量类型转换为整数。
一个有返回值的函数，如果执行了return语句，函数直接结束，不需要再break。
定义一个常量大小的数组，空间复杂度是O(1)。

349. 两个数组的交集

set, multiset, unordered_set。前两者底层实现是红黑树，最后一个的底层实现是哈希值直接映射。unordered_set就是一个可以无限存装的数组。本题用unordered_set，因为其做映射和取值时效率最高，前两者的底层实现是树，因此取值是还要有查找的过程。unordered_set中的元素不可重复，相当于自动帮我们做去重；而multiset中的元素可以重复。
可以直接将set类型的数据转换为vector类型：return vector<int>(set.begin(), set.end())。
cpp中的vector中既有insert方法，又有push_back方法，前者需要指定插入元素的具体位置，后者直接将元素插入到vector的末尾。cpp的set（包括set, multiset, unordered_set）中只有insert方法，传入的参数为要插入的值，不需要指定插入元素的具体位置。
将vector转换为unordered_set: unordered_set<int> nums1_set(nums1.begin(), nums1.end())。
在unordered_set中查找元素：nums1_set.find(nums2[i])，返回的结果是一个迭代器（指针）。如果找到该值，find返回一个指向该元素的迭代器；如果未找到，则返回一个指向unordered_set末尾的迭代器，即end()迭代器。

1. 两数之和

返回一个vector可以直接将vector的内容写入大括号中，然后返回，比如return {a[i], b[i]}，返回一个空数组可以直接写成return {}，而不用定义一个vector再利用push_back方法向其中插入数，然后再返回这个vector。
定义的vector<int> a，若不给其赋值，则该vector长度为0。可见vector是动态地被分配内存，如果不给其赋值，则其长度为0，不占用内存，这与普通数组需要在定义时声明长度有所不同。
定义unordered_map的方式：unordered_map<int, int> map；unordered_map中有insert函数和find函数，用法同unordered_set；遍历这些STL容器都要用迭代器，相当于是一种加强版的指针；访问unordered_map的key和value：map->first和map->second。

初次尝试

242.有效的字母异位词

想到一个办法，用两个数组分别统计两个字符串中出现的字母和字母出现的频次，然后判断两个数组是否完全相同。代码如下所示，可以成功运行：

class Solution {
public:
    bool isAnagram(string s, string t) {
        int hash1[26] = {0};
        int hash2[26] = {0};

        for (int i = 0; i < s.size(); i ++ )
            hash1[s[i] - 'a'] ++ ;

        for (int i = 0; i < t.size(); i ++ )
            hash2[t[i] - 'a'] ++ ;

        for (int i = 0; i < 26; i ++ )
            if (hash1[i] != hash2[i])
                return false;
        return true;
    }
};

稍微麻烦了点，实际上用一个数组就够了。

349. 两个数组的交集

暂时还不会用set做哈希，因此先尝试用数组做哈希。我写下了如下的代码：

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        int hash1[1000] = {0};
        int hash2[1000] = {0};

        // 统计两个数组nums1和nums2中每个数值出现的频次
        for (int i = 0; i < nums1.size(); i ++ )
            hash1[nums1[i]] ++ ;
        for (int i = 0; i < nums2.size(); i ++ )
            hash2[nums2[i]] ++ ;

        vector<int> res;

        // 若一个数同时在nums1和nums2数组中出现的频次>=1，则该数是两数组的重叠，放入结果数组res中
        for (int i = 0; i < 1000; i ++ )
        {
            if (hash1[i] && hash2[i])
                res.push_back(i);
        }
        return res;
    }
};

本题其实是使用set的好题，但是后来力扣改了题目描述和测试用例，添加了 0 <= nums1[i], nums2[i] <= 1000 条件，所以使用数组也可以了，不过建议大家忽略这个条件。尝试去使用set。

202. 快乐数

尽管说这道题和上一道题原理上差不多，只是套了快乐数的壳子，但我看不出这题怎么用set来进行哈希。直接看讲解吧。

1. 两数之和

看到的第一想法是类似滑动窗口，但滑动窗口（209.长度最小的子数组）返回的是长度最小的子数组的长度，这道题却要返回两个整数的下标，因此还是有很大不同的。如果要快速在集合中查找一个元素是否出现过，那么应该采用哈希表的方法。我产生了一个想法，将nums数组中的所有数一对一对不重不漏地取出，将每一对数的和作为索引（key），将它们的下标作为（value）存入map中，然后通过查询map的索引来找到目标对，进而返回目标对的下标。实现起来有两个难点：

如何不重不漏地枚举所有的数对？
如何将两个下标存入一个value里？

实现

242.有效的字母异位词

判断两个字符串是否由相同的字母组成，但字母的位置可以不同。两个完全一样的字符串也是有效异位词。由于字符串中都是小写字母，因此a可以对应数组中索引为0的位置，z可以对应数组中索引为25的位置。用数组hash[26]统计第一个数组中每个字母出现的频率，然后第二个字符串中每个字母出现的频率再在hash数组中做对应的减法，若最后数组中所有元素均为0，则说明两个字符串互为有效的字母异位词。

什么时候用数组/set/map：当哈希值较小，且范围也较小且可控；若哈希值很大，则用set；若是key-value对，则用map。

根据上述思路，我独立写出了代码，如下所示：

class Solution {
public:
    bool isAnagram(string s, string t) {
        int hash[26] = {0}; // 数组中的元素全部初始化为0

        for (int i = 0; i < s.size(); i ++ )
            hash[s[i] - 'a'] ++ ;

        for (int j = 0; j < t.size(); j ++ )
            hash[t[j] - 'a'] -- ;

        for (int i = 0; i < 26; i ++ )
            if (hash[i])
                return false;
        return true;
    }
};

349. 两个数组的交集

返回两个数组的交集。注意要去重。虽然可以用数组哈希，但还是建议用set。若保持之前的题目描述，让两个数组中的数值可能非常大，比如上亿，此时就必须要用set了，因为数组下标放不下那么大的数，同时会浪费很多存储空间。

哈希表善于解决判断一个元素是否在一个集合中出现过的题目。集合中的数值很大时，或者集合中的元素数量很少但数值很分散时，用数组不合适，要用set。先将数组nums1中的所有数值放到哈希表中，再遍历num2，查看其中的元素的数值是否在哈希表中出现过，出现过则放入res集合中。

因为要去重，所以定义unordered_set来存储result。哈希表也用unordered_set。直接将nums1转化为unordered_set的存储结构。接着遍历nums2，看哈希表中是否出现了nums2中的元素，出现了则将其放入result中。

代码如下所示：

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        // 存储答案的unordered_set，因为是unordered_set所以自动去重
        unordered_set<int> res; 

        // 将nums1从vector转换为unordered_set
        unordered_set<int> nums1_set(nums1.begin(), nums1.end());

        // 在nums1_set中查找nums2中的数据，如果出现过，则将其插入res中
        // 也可以用范围遍历for (int num: nums2)
        for (int i = 0; i < nums2.size(); i ++ )
        {
            if (nums1_set.find(nums2[i]) != nums1_set.end())
                res.insert(nums2[i]);
        }
        
        // 将res从unordered_set类型转换回vector类型
        return vector<int>(res.begin(), res.end());
    }
};

时间复杂度：
构建nums_set：O(n)
遍历nums2并检查元素是否在nums_set中：O(m)
构建结果向量：O(k)，其中k是结果集中元素的数量
综上所述，总的时间复杂度是O(n + m + k)。但是由于k（结果集的大小）是由n和m决定的，并且在大多数情况下k会小于n和m，所以可以近似地认为时间复杂度主要由n和m决定，即O(n + m)。

如果用数组做哈希的话，除了我在初次尝试中写的那种方式，其实还有另一种方式。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> res; // 存储结果，去重

        int hash[1000] = {0};

        // nums1中出现过的数，则将其在哈希数组中的值标记为1
        for (int num: nums1)
            hash[num] = 1;

        // 若nums2中的数在nums1中出现过，则将其插入res中  
        for (int num: nums2)
            if (hash[num] == 1)
                res.insert(num);
                
        // unordered_set->vector
        return vector<int>(res.begin(), res.end());
    }
};

202. 快乐数

题目中说：Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.本题本来是一个数学问题，可以得到严格的数学证明，但我们不需要懂数学，可以用编程的思维去解决它。

因此，一个数进行如题的操作后，要么会陷入死循环，要么会在某个时刻等于1并保持。因此，可以写一个循环来持续对输入的数进行如题的操作，如果某次操作的结果在之前出现过，那么该数就不是快乐数；如果操作的结果为1，那么该数就是快乐数。要快速判断一个元素是否在集合中出现过，就应该用一个set将集合中的所有元素维护起来。代码如下所示：

class Solution {
public:
    // 用于求一个数每一位的平方之和的函数
    int getSumofDigits(int n)
    {
        int s = 0;

        while (n)
        {
            s += (n % 10) * (n % 10); // 求每一位的平方
            n /= 10;
        }
        return s;
    }

    bool isHappy(int n) {
        unordered_set<int> loop;

        // 持续循环
        while (1)
        {
            int s = getSumofDigits(n);

            if (s == 1) return true; // 结束循环，是快乐数
            else
            {
                // 若发现出现死循环，则立即返回不是快乐数
                if (loop.find(s) != loop.end()) return false;
                // 尚未出现死循环，则继续
                else 
                {
                    loop.insert(s);
                    n = s;
                }
            }
        }
    }
};

可以将上述代码写得更见简练，更好理解：

class Solution {
public:
    int getSum(int n)
    {
        int s = 0;

        while (n)
        {
            s += (n % 10) * (n % 10);
            n /= 10;
        }
        return s;
    }

    bool isHappy(int n) {
        unordered_set<int> set;

        while (1)
        {
            int s = getSum(n);

            if (s == 1) return true; // 退出条件1，是快乐数
            if (set.find(s) != set.end()) return false; // 退出条件2，不是快乐数

            // 不满足两个退出条件，则继续循环
            n = s;
            set.insert(s);
        }
    }
};

这里主要处理的是数字 n 的每一位，一个数字n它的位数可以认为是logn（一个d位的数大约是10的d次方，n = 10^d => d = logn）。每次进行快乐数的判断会执行一次该计算操作，但是因为快乐数的范围有限，总体来看不会超过 logn 的常数倍，因此时间复杂度是O(log n)。

所以随着n的增加，存储在unordered_set中的不同可能结果的数量实际上是有限的。事实上，随着n的增长，这个数量的增长速度接近于对数增长。换句话说，即使n非常大，经过getSum处理后的结果仍然是一个相对较小的数字集合。因此空间复杂度为O(logn)。至于为什么是logn，我认为原因是其增长速度最慢，这比sqrt(n)等其他形式更符合n较大时set中存储的元素的数量接近一个常数的事实。

1. 两数之和

本题需要用map解决。判断一个元素是否在一个集合中出现过：用哈希法。假设target = 9，当遍历到元素3时，我们需要去寻找元素6是否被遍历过。把遍历过的元素加到一个集合（哈希表结构）中，每次遍历新元素a时，判断(target - a)是否在集合中出现过。若出现过，我们需要知道其下标，因此集合中既要存储元素的值，又要存储元素的下标。此时想到用map，存储元素的值用map的key，存储元素的下标用map的value（因为要查找元素是否出现过，因此以元素的值作为key，map能以最快的速度找到这个key是否在这个map中出现过）。

看完上述思路后，我独立写出了以下的代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> store;
        vector<int> res;

        // 将所有元素的值作为key，索引作为value存入map中
        for (int i = 0; i < nums.size(); i ++ )
            store.insert({nums[i], i});

        // 每遍历到一个元素nums[i]，查找target - nums[i]是否在map中
        // 是则返回结果
        for (int i = 0; i < nums.size(); i ++ )
        {
            int t = target - nums[i];
            auto it = store.find(t);

            // 注意除去第一个条件外，还需要保证查找到的元素并非当前元素本身
            // 否则会出现target = 两倍当前元素而导致的误判
            if (it != store.end() && it->second != i)
            {
                res.push_back(i);
                res.push_back(it->second);
                return res;
            }
        }
        return res;
    }
};

继续听讲解，map用于存放遍历过的元素的值和索引。本题使用unordered_map，其存和读的效率是最高的。因此写出了以下的代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> store;
        vector<int> res;

        // 每遍历到一个元素nums[i]，查找target - nums[i]是否在map中
        // 是则返回结果
        for (int i = 0; i < nums.size(); i ++ )
        {
            int t = target - nums[i];
            auto it = store.find(t);

            // 若找到了target - nums[i]，则将其索引和当前遍历的元素的索引返回
            if (it != store.end())
            {
                res.push_back(i);
                res.push_back(it->second);
                return res;
            }
            // 将已经遍历过的元素的值作为key，索引作为value存入map中
            store.insert({nums[i], i});
        }
        return res;
    }
};

我的第一版代码在store中存储了数组中所有元素的值和索引，因此需要保证查找到的元素并非当前元素本身。第二版代码在store中存储的是已经遍历过的元素，故天然满足查找到的元素并非当前元素本身的条件。两版代码都是对的，但后者更为简洁。最简洁版本的代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map; // 用于存储已遍历过的元素的值和索引

        for (int i = 0; i < nums.size(); i ++ )
        {
            // 用于查找map中是否有目标元素
            auto it = map.find(target - nums[i]);
            // 有，则返回两个索引构成的vector
            if (it != map.end()) return {i, it->second};
            // 无，则将当前元素的值和索引插入map中，然后开始循环的下一轮
            map.insert({nums[i], i});
        }
        // 完成循环后还没找到两个索引，则返回空vector
        return {};
    }
};

心得与备忘录

242.有效的字母异位词

本题的本质是判断两个字符串是否由相同的字母组成。
本题用数组实现哈希。
遇到哈希问题时，首先想想能不能用数组做哈希。用数组做哈希最直接，运行速度也最快，用set做哈希速度更慢，但遇到大规模的索引，数组放不下时，只能用set。

349. 两个数组的交集

本题本来不改测试数据，数组中的数值可能很大时，只能用set做哈希。现在对数组中的数值做了限制，最大不超过1000，则可以用数组做哈希。
用数组做哈希比用set做哈希效率更高，因为用set的话每次往里Insert一个值，都需要对这个值做一次哈希运算，同时还要开辟一个新的空间。用数组的下标做哈希映射永远是最快的。
本题适合用来衔接用数组做哈希和用set做哈希。
本题用set做哈希时，要记住set的各种用法：vector和unordered_set互相转化，在unordered_set中查找元素。这些用法归纳在知识中。
本题有三种解法：一种是用set哈希，另外两种是用数组做哈希。用数组做哈希建议采用我在初次尝试中的做法，只需要用到数组，不需要用到unordered_set去重。
采用范围遍历的写法可以简化代码。

202. 快乐数

这道题的逻辑其实非常简单。若各个位上的平方和为1，则退出循环，返回是快乐数；若平方和之前出现过，则说明进入了死循环，也退出循环，返回不是快乐数；其他情况下，继续循环。由于本题的1 <= n <= 2^31 - 1，各个位的平方和的数据范围非常大，因此必须用set做哈希，不能再用数组做哈希。注意本题时间复杂度和空间复杂度的分析。时间复杂度和空间复杂度不存在sqrt(n)等表达式，要么是1, 要么是logn，要么是n，要么nlogn或者更大。

1. 两数之和

四个重要问题：

为什么用哈希法：快速查找一个元素（目标元素）是否在集合（unordered_map存放已遍历过的元素）中出现过。
为什么要用map（unordered_map）：因为既需要存储元素的值，也需要存储元素的索引。这道题目中并不需要key有序，选择unordered_map 效率更高。
map的作用：存储已遍历过的元素的值和索引。
map中的key存了元素的值（便于查询），value存了元素的索引（作为结果返回）。