【代码随想录】算法训练营 第五天 第三章 哈希表 Part 1

目录

哈希表理论基础

242. 有效的字母异位词

题目

思路

代码

349. 两个数组的交集

题目

思路

代码

202. 快乐数

题目

思路

代码

1. 两数之和

题目

思路

代码

无序集合解法

map解法

---

哈希表理论基础

哈希表就是之前在数据结构中学过的散列表，通过哈希表可以实现快速查找，只要提供key值，就可以直接找到对应的value，这个和数组的根据下标直接得到数组元素异曲同工。

哈希表还涉及到元素存储的问题，如果不同值对应的下标相同时，避免出现这种名为哈希碰撞的bug的方法有两个，首先是将哈希表的每个表位置设置为链表的头结点，这样出现相同映射时就可以将其他值放到头结点之后。还有一个方法叫做线性探测，这种方法是要存的元素比哈希表容量小时可以使用，就是要存一个元素的时候，发现这个位置已经被占了，就可以往下寻找，有空位就可以放进去。

当我们想要用哈希表来解决问题时，一般会选择下面这三种数据结构：

• array 数组
• set 集合
• map 映射

当我们需要判断一个元素是否出现在集合里时，就要立马想到哈希法，而且，使用哈希表是一种用空间换时间的方法，因此才能实现快速查找。

242. 有效的字母异位词

题目

思路

两个字符串就是两个数组，要提取出数组中所有不同的值，还要记录出现的次数，首先想到的就是哈希表，不同的字母就是不同的key，字母出现的次数就是value，这里给出的字符串中只有26个小写字母，所以工作量并不大，把26个字母映射为26个数就行。

所以，先开一个长度为26的数组，数组中的元素全部赋值为0，便于后续对每个字母的出现进行计数；

接着，先遍历第一个字符串，每遍历到一个位置都要将这个位置的字母映射为数组的一个下标，这里的映射很简单，因为26个小写字母在ASCII表中是从a开始连续排列的，所以只需要把每个字符串元素减去字符 'a' ，就可以得到它们的相对位置了，用这个相对位置来作为它们在数组中的下标即可；

遍历第一个字符串时，每遇到一个字母，就在相应的数组元素中加一；遍历第二个字符串时，每遇到一个就减一。这样到最后，如果数组中所有元素都为0，就说明两个字符串满足条件，返回true，只要有一个不为0，就直接返回false，这个用遍历就可以实现。

代码

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

349. 两个数组的交集

题目

思路

这道题中涉及到的数据范围太大了，不像上面只有二十六个小写字母，如果使用数组的话会导致空间利用率太低，除此之外，我们还看到题目中说，输出结果中每个元素都是唯一的，这意味着需要我们去重，而且不用考虑结果的输出顺序；

提高空间利用率 + 去重 + 不考虑顺序，这一切都指向一个STL容器，名为 unordered_set，作为无序集合，它可以用来去重，既然需要使用这个容器，我们就需要了解它的一些简单操作：

接下来操作就很简单了，我们先把一个数组转换为集合，再遍历另一个数组，如果另一个数组中的元素出现在集合中，我们就把这个元素添加到结果集合里。

代码

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; // 用集合可以去重
        unordered_set<int> nums_set(nums1.begin(), nums1.end()); // 第一个数组去重后的集合
        for (int num : nums2) {
            if (nums_set.find(num) != nums_set.end()) { // 找到就返回这个元素的迭代器，没找到就返回指向end的迭代器
                result_set.insert(num); // 往unordered_set里添加元素用的是num
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

202. 快乐数

题目

思路

这道题就跟中学时做过的规律题一样，每次运算后会得到一个数，如果这个数之前出现过，就说明之后的运算会进入循环，我们可以使用集合来存储每次新出现的数，并通过不断的循环来判断有没有旧数出现，如果出现了，那就直接返回false，但是如果计算出结果为1，就返回true。

代码

class Solution {
public:
    int getsum(int n) {
        int sum = 0;
        while(n) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> set;
        while (1) {
            int sum = getsum(n);
            if (sum == 1) {
                return true;
            }
            if (set.find(sum) != set.end()) {
                return false;
            }
            else {
                set.insert(sum);
            }
            n = sum;
        }
    }
};

1. 两数之和

题目

思路

我是使用unorder_set来做的，用这个方法需要对两个数相等的情况进行特判，所以麻烦了一点，但好歹也是我自己做出来的，所以下面也会放上我的解法，算是正反馈；

而卡哥则是用map来做。map相当于python里的字典，我们每次可以存入一对数据，前者是key，后者是value，对应这道题里的数组元素和下标，因为我们查找过程中用到的是数组元素，但是最后返回的是下标，所以这里用map最合适不过了。

map的用法详见代码随想录，需要记得是，当题目中的查询涉及到一对相关联的数据时，最好使用map，因为数组只适用于数据较少时，集合只存元素，不存下标，这都对本题的解答不利，虽然我用set也勉强解出来了。

map解法的思路和我的无序集合解法基本一致，遍历所有元素，每遍历一个元素后就将其存入map，还要查询map里是否有与其相补的元素，如果有的话，就返回两者的下标组成的数对pair，这就避免了当两个满足条件的元素相等时所需要的特判。

代码

无序集合解法

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_set<int> set(nums.begin(), nums.end());
        vector<int> result1, result2;
        int n = 0;
        for (int i = 0; i < nums.size(); i++) {
            int num = target - nums[i];
            if (set.find(num) != set.end() && num != nums[i]) {
                result1.push_back(i);
            }
        }
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] * 2 == target) {
                result2.push_back(i);
                n++;
            }
        }
        if (n == 2)
            return result2;
        else
            return result1;
    }
};

map解法

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::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};
            }
            map.insert(pair<int, int>(nums[i], i));
        }
        return {};
    }
};