day6 哈希有效的字母异位词两个数组的交集快乐数两数之和-Toy模板网

这篇具有很好参考价值的文章主要介绍了day6 哈希有效的字母异位词两个数组的交集快乐数两数之和。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

- day5周日休息
---

哈希表
- 什么时候用
   - 需要记录对比数据，判断数据是否在集合里面
- 哈希三种形式
   1. 数组
       - 记录一个数
       - 已知长度，belike 26个字母
       - 已知最大长度，且长度较小，belike 1 <= num <= 1000
   2. set
       - 记录一个数
       - 除了数组外的其它
           - 用数组的地方用set也可以，但是浪费
   1. map
       - 记录一组数，需要用key->value，belike 数组通过数值判断下标
   - 用不用 unordered，看哈希表需不需要顺序记录
---

- 有效的字母异位词
   - 26个字母，用数组即可
```cpp
class Solution {
public:
    bool isAnagram(string s, string t) {
        int table[26] {0};
        for (int i = 0; i < s.size(); i++) {
            table[s[i] - 'a']++;
        }
        for (int i = 0; i < t.size(); i++) {
            table[t[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (table[i])
                return false;
        }
        return true;
    }
};
```

- 两个数组的交集
   - `0 <= nums1[i], nums2[i] <= 1000`，用数组即可
   - unordered_set记录出现过的数字，这样就不会重复记录，如果用数字，会出现`[2,2]`这种结果
```cpp
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        int hash[1001] {0};
        unordered_set<int> ret;
        for (int i : nums1) {
            hash[i]++;
        }
        for (int i : nums2) {
            if (hash[i]) {
                ret.insert(i);
            }
        }
        return vector<int>(ret.begin(), ret.end());
    }
};
```

- 快乐数
   - O(log n)
       - 计算出第一个平方和的时间是log n，再下一个是log log n，取大头所以是log n
   - 平方后的数有两种情况
       - 为1
       - 无限循环，即会出现与之前相同的数，所有用哈希表记下来，每次对比是否出现重复即可
   - 不知道到底多次，记录一个数，用set
```cpp
class Solution {
public:
    int getQuartSum(int n) {
        int sum = 0;
        while (n) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> record;
        while (1) {
            int quartSum = getQuartSum(n);
            if (quartSum == 1) return true;
            if (record.count(quartSum)) {
                return false;
            }
            record.insert(quartSum);
            n = quartSum;
        }
    }
};
```

- 两数之和
   - 找俩数相加为target，即在遍历到num时，过去已经遍历的数是否存在 target - num
   - 返回下标，即通过数值寻找对于的下标，即key -> val，用map
```cpp
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;
        for (int i = 0; i < nums.size(); i++) {
            auto it = map.find(target - nums[i]);
            if (it != map.end()) {
                return {it->second, i};
            }
            map.insert(make_pair(nums[i], i));
        }
        return {};
    }
};
```文章来源地址https://www.toymoban.com/news/detail-603466.html