湖南省网站建设项目网站关键词推广企业
先验知识记录：
遇到哈希问题，想到三种数据结构：
①数组：适用于哈希值比较小，范围较小，
②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;//方法1set<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;//方法2int hash[1001]={0};//遍历nums1，若有数字，则为1for(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;
}