Day5 哈希的一天

By HQWQF 2023/12/13

当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

笔记

242.有效的字母异位词

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

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

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

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

解法：简单hash表

我们可以使用长度26的数组（在这里相当于hash表）记录字符串中所有字母出现的次数。然后对比两个字符串中所有字母出现的次数情况，情况一致则为字母异位词。由于记录字母次数的数组可以通过字母的ascii码来直接定位到存储该字母出现次数的位置，这种数组符合哈希表的定义。

哈希表就是可以直接通过某个值来获取值的存储位置的表

代码

class Solution {
public:
    bool isAnagram(string s, string t) {
        int strhash_1[26] = {0};
        int strhash_2[26] = {0};
        for(int i = 0;i<s.size();i++)
        {
            strhash_1[(int)s[i]-97]++;
        }
        for(int i = 0;i<t.size();i++)
        {
            //(int)t[i]-97就相当于hash函数其实这种写法对c++来说没什么必要，直接t[i]-‘a’就行
            strhash_2[(int)t[i]-97]++;
        }
        for(int i = 0;i<26;i++)
        {
            if(strhash_1[i] != strhash_2[i])
            {
                return false;                
            }       
        }
        return true;
    }
};

还有一种方法可以节省一个数组的空间

class Solution {
public:
    bool isAnagram(string s, string t) {
        int record[26] = {0};
        for (int i = 0; i < s.size(); i++) {
            // 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
            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) {
                // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
                return false;
            }
        }
        // record数组所有元素都为零0，说明字符串s和t是字母异位词
        return true;
    }
};

349. 两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是唯一的。我们可以 不考虑输出结果的顺序 。

示例 1：

输入： nums1 = [1,2,2,1], nums2 = [2,2]输出：[2]

示例 2：

输入： nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出：[9,4]
解释：[4,9] 也是可通过的

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

解法：使用内置的哈希表结构

上一题使用数组来做哈希的题目，是因为题目在数值的跨度在一个比较小的范围内（26），如果对于数据跨度大或者不给出数据范围的题目我们再用数组做哈希表，就会面临一个很长的hash表，其中有很多的空位，所以就要使用C++内置的数据结构——集合set。

关于set，C++ 给提供了如下三种可用的数据结构：

std::set
std::multiset
std::unordered_set

集合unordered_set在内置的哈希表中，读写效率最高，数据不排序，其中的数据不会重复。

然而unordered_set虽然读写效率相对高，但在数组合适的时候还是不如数组。这题的范围在1000内，使用数组还会快一些。

使用unordered_set

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; // 存放结果，之所以用set是为了给结果集去重
        //将一个列表转化为集合可以去重
        unordered_set<int> nums_set(nums1.begin(), nums1.end());
        for (int num : nums2) {
            // 发现nums2的元素 在nums_set里又出现过
            if (nums_set.find(num) != nums_set.end()) {
                //因为result_set是集合，就算多次insert相同的数也没事
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

使用数组

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; // 存放结果，之所以用set是为了给结果集去重
        int hash[1005] = {0}; // 默认数值为0
        for (int num : nums1) { // nums1中出现的字母在hash数组中做记录
            hash[num] = 1;
        }
        for (int num : nums2) { // nums2中出现话，result记录
            if (hash[num] == 1) {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

202. 快乐数

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

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

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

解法：哈希表

注意题目中的一个词无限循环，循环意味着会出现曾经出现过结果，如果我们将每次计算位平方和的结果于哈希表对比并存储，如果出现重复则说明进入了无限循环，这个数就不是快乐数，快乐数在循环后必定会得到1。

代码

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;
            }
            // 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return false
            if (set.find(sum) != set.end()) {
                return false;
            } else {
                set.insert(sum);
            }
            n = sum;
        }
    }
};

1. 两数之和

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

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

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

解法：哈希表 map

遍历数组中的元素，检查值=target-当前的元素的元素是否存在于哈希表中（把已经遍历到的元素加入不可重复的哈希表中），如果存在则找到了答案，将元素下标保存。由于我们需要返回的是元素的下标，我们要用存储键值对的哈希表map来解决这个问题。

这道题很明显的暴力解法是两层for循环查找，时间复杂度是O(n^2)，我们可以发现这样的解法的重复之处：

暴力解法

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res(0);
        for(int i = 0 ;i < nums.size();i++)
        {
            for(int j = 0 ;j < nums.size();j++)
            {
                if(i == j){continue;}
                if(i == j){continue;}
                if(nums[i]+nums[j] == target)
                {
                    res.push_back(i);
                    res.push_back(j);
                    return res;
                }
            }   
        }
        return res;
    }
};

如，对于一个nums[i]而言，它要加的nums[j]在数值可能是和其他nums[j]是重复的。另外nums[i]+nums[j]在i和j数值交换的情况下是相等的，我们没必要去计算两次。

总之，我们重复验证了一些我们已经验证过的数字组合。

那么如果我们在一次遍历数组的过程中，将已经遍历的元素加入一个去重的哈希表中，我们只需要检测这个哈希表中有没有元素加上当前元素等于目标值（对于哈希表来说这个操作是O(1)的），这样我们就只需要一层循环了。

值得注意的是我们需要的是下标，因此我们需要使用要用存储键值对的哈希表map来解决这个问题。

C++中map，有三种类型：

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

由于我们不需要有顺序。这里使用unordered_map，key存储遍历过的元素值，value存储相应的下标

哈希法

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++) {
            // 在去重的map中寻找是否有匹配的key
            auto iter = map.find(target - nums[i]); 
            if(iter != map.end()) {
                return {iter->second, i};
            }
            // 如果没找到匹配对，就把访问过的元素和下标加入到map中
            map.insert(pair<int, int>(nums[i], i)); 
        }
        return {};
    }
};