代码随想录算法训练营第六天| 哈希表理论基础、242.有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和

常见的三种哈希结构：vector数组、set （集合）、map(映射)

哈希表理论基础

常见的三种哈希结构：vector数组、set （集合）、map(映射)

242.有效的字母异位词

固定类别的存储内查找用固定大小的vector；
思路：
1、26种英文字符分别记录两字符串中各种字符的数量；
2、若两字符串相互抵消，则最终vector元素全为0

固定大小的vector

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

349. 两个数组的交集

一、set的使用：
1、初始化 unordered_set antherNum(nums1.begin(),nums1.end());
2、查找特定元素 antherNum.find(nums2[i]) != antherNum.end()；
二、思路：
1、先用一个set1保存数组1的元素
2、遍历数组2的元素若存在于set1，则将元素加入交集set2（消除重复元素）

unordered_set

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> antherNum(nums1.begin(),nums1.end());
        unordered_set<int> result{};
        for(int i = 0; i < nums2.size(); i++){
            if(antherNum.find(nums2[i]) != antherNum.end()){
                result.insert(nums2[i]);
            }
        }
        vector<int> resultV(result.begin(),result.end());
        return resultV;
    }
};

202. 快乐数

一、int getNewnum(int num)：%除余操作获取每位数字
二、思路：
1、结束循环：确定是快乐数（1）或不是快乐数（出现重复数）
2、将已出现的数加入unordered_set集合，从而用来判断是否重复实现；

unordered_set

class Solution {
public:
    int getNewnum(int num){
        int sum = 0;
        while(num != 0){
            sum += (num%10)*(num%10);
            num /= 10;
        }
        return sum;
    }

    bool isHappy(int n) {
        if(n == 1) return true;
        unordered_set<int> getedNum{n};
        int newNum = getNewnum(n);
        while(newNum != 1){
            if(getedNum.find(newNum) != getedNum.end()) return false;
            getedNum.insert(newNum);
            newNum = getNewnum(newNum);
        }
        return true;
    }
};

1. 两数之和

一、unordered_map的使用：
1.初始化：unordered_map<int,int> anotherNums;
2.查找特定元素：anotherNums.find(nums[i]) != anotherNums.end()
3.映射的元素 pair<int,int>(target - nums[i],i)
二、思路
1、遍历数组，将目标值和当前元素值的差值、当前元素下标保存到unordered_map映射中
2、遍历数组时在unordered_map映射中寻找相同值的差值，组成一对两数之和为目标的元素下标

unordered_map

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> anotherNums;
        vector<int> result(2);
        for(int i = 0; i < nums.size();i++){
            if(anotherNums.find(nums[i]) != anotherNums.end()){
                result[0] = anotherNums[nums[i]];
                result[1] = i;
            }
            else{
                anotherNums.insert(pair<int,int>(target - nums[i],i));
            }
        }
        return result;
    }
};