个人技术分享

先验知识记录：

遇到哈希问题，想到三种数据结构：

①数组：适用于哈希值比较小，范围较小，

②set：适用于哈希值较大。

③map：如果需要用到键值对，则用之。

---

242.有效的字母异位符。

代码随想录链接

力扣链接

问题描述：

就是看两个字符串里面的字符是不是一样的，它们包含的字母以及个数是否是一致的。

思路：

因为单个字母总共有26个，所以建立数组形式的hash表。初始的hash表各个元素为0。经过字符串1的遍历后，hash表此时对应位置的字母数为字符串1的字母数。

再去遍历字符串2，如果遍历后的hash字母表存在字母对应的值不为0，则说明两个字符串包含的字母及字母数不同。如果每个hash表中每个位置的字母都为0，那么说明两个字符串中是异位关系。

注意，此时hash表中的字母位置，使用hash[string1[i]-'a']表示，这个很妙，因为这就相当于取出字符串每个字符对应到hash数组中且一一对应。

伪代码：

新建数组hash字母表
遍历字符串1
	对对应位置的hash字母表数值+1，表示字符串1中的hash字母表中字母个数
遍历字符串2
	对对应位置的hash字母表数值-1，表示字符串2中的hash字母表字母个数-字符串1中对应位置的字母个数
遍历hash字母表
	如果某个位置不为0
		说明两个字符串不是异味关系，返回false
遍历完成后，返回true

代码：

bool isAnagram(string s, string t) {

    int hash[26]={0};

    for(int i  =0 ; i<s.size();i++){
        //遍历字符串s，使得s对应的字母表每个都有其对应次数。
        //s[i]就是s的每个字符，s[i]-‘a’代表了其对应哈希表的索引从0-25。字符串t同理。
        hash[s[i]-'a']++;
    }
    for(int i = 0 ; i< t.size() ; i++){
        hash[t[i]-'a']--;
    }
    for(int i = 0 ; i < 26; i++){
        if (hash[i]!=0){
            return false;
        }
    }
    return true;
}

---

349.两个数组的交集。

代码随想录链接

力扣链接

问题描述

两个数组，取交集，最后的结果要不重复。

思路：

有两种思路解决：

①set，将数组1的元素存入set去重。遍历数组2，如果元素在set中，则放入另个集合中，作为返回值返回。

遍历数组1，将数组中每个元素去重后放入number_set中
遍历数组2
	如果数组2中有元素在number_set中
		则放入result_set中
将result_set转为vector，作为返回值返回

②数组，力扣上有数组中单个元素大小限制，故将hash表数组设置为1000出头的大小。

新建hash表，大小为1000出头
遍历数组1
	对数组1的每个元素放到hash数组中，为1.
遍历数组2
	如果数组中有数字对应hash值为1
		将元素放入result_set中
将result_set转为vector，作为返回值返回

解法①代码：

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    set<int> result_set;
    
    //方法1
    set<int> number_set ;
    for(int i = 0 ; i < nums1.size() ; i++){
        number_set.insert(nums1[i]);
    }
    for(int i = 0 ; i< nums2.size();i++){
        if (number_set.find(nums2[i])!= number_set.end()){
            result_set.insert(nums2[i]);
        }
    }
    vector <int> vt;
    vt.assign(result_set.begin(),result_set.end());
    return vt;
}

解法②代码：

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    set<int> result_set;

    //方法2
    int hash[1001]={0};
    //遍历nums1，若有数字，则为1
    for(int i = 0 ; i < nums1.size() ; i++){
        hash[nums1[i]]=1;
    }
    for(int i = 0 ; i < nums2.size();i++){
        if (hash[nums2[i]]){
            result_set.insert(nums2[i]);
        }
    }

    vector <int> vt;
    vt.assign(result_set.begin(),result_set.end());
    return vt;
}