【力扣一轮】字符串异位 数组并集

先验知识记录：

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

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

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