记住且谨记一句话：当遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。

哈希表理论基础

回头自己看相关理论基础吧，或者菜鸟教程里的都可以。

[代码随想录](https://programmercarl.com/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E5%93%88%E5%B8%8C%E8%A1%A8)

力扣242：有效的字母异位词

题目描述

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

示例 1:

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

示例 2:

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

注：所谓字母异位词：是指将词语中的字母重新组合排列，每次字母只能使用一次，而重新排列组合得到的新的词语。

解题思路

为了方便举例，判断一下字符串s= "aee", t = "eae"。

操作动画如下：

242.有效的字母异位词

定义一个数组叫做record用来上记录字符串s里字符出现的次数。

需要把字符映射到数组也就是哈希表的索引下标上，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。

再遍历 字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了。 这样就将字符串s中字符出现的次数，统计出来了。

那看一下如何检查字符串t中是否出现了这些字符，同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作。

那么最后检查一下，record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false。

最后如果record数组所有元素都为零0，说明字符串s和t是字母异位词，return true。

时间复杂度为O(n)，空间上因为定义是的一个常量大小的辅助数组，所以空间复杂度为O(1)。

//想出这种解法的人真是天才，借助于哈希表，先统计第一个数组的特征值，-'a'的操作真是太妙了，因为这样对于没记住a的ascll码值真是太友好了，这种方法更具有通用性。再使用前一个字符串所得的特征值逐个减去所要判断的字符串，判断最后的结果是否为0。果然搞算法的人都是天才！

完整代码

构建数组，或者说是构建哈希表。

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

        //开始统计数/或者说是开始使用数组s来形成哈希表
        for(int i = 0; i < s.size(); i++){
            record[s[i] - 'a']++;
        }

        //开始利用t字符串来逐步清楚哈希表
        for(int j = 0; j < t.size(); j++){
            record[t[j]-'a']--;
        }
  
        //开始进行判断
        for(int i = 0; i < 26; i++){
            if(record[i] != 0){
                return false;
            }
        }
        return true;
    }
};

力扣202：快乐数

题目描述

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

「快乐数」 定义为：

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

如果 n 是 _快乐数_ 就返回 true ；不是，则返回 false 。

示例 1：

**输入：n = 19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

示例 2：

**输入：n = 2
输出：false**

解题思路

首先计算给定整数的单数之和；之后进行判断是不是快乐数。判断为真很方便，重点是判断为假的情况，还要处理陷入循环的情况。

完整代码

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，请你在该数组中找出 和为目标值 _target_  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。
![[附件/Pasted image 20250715230404.png||800]]

解题思路

完整代码


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 {};
    }
};

本日小结

  • 202题目的判断部分还需要重新理解，一是不同类型哈希表的选择标准，二是具体实现。