哈希法学习

哈希法，常用数据结构：数组，set，map（unordered_set,unordered_map）

1.用数组

242. 有效的字母异位词 - 力扣（LeetCode） (leetcode-cn.com)

 1 class Solution {
 2 public:
 3     bool isAnagram(string s, string t) {
 4         if(s.length()!=t.length())
 5             return false;
 6         int a[26]={0};
 7         for(int i=0;i<s.length();i++){
 8             a[s[i]-'a']++;
 9             a[t[i]-'a']--;
10         }
11         for(int i=0;i<26;i++){
12             if(a[i]!=0)
13                 return false;
14         }
15         
16         return true;
17     }
18 };

View Code

2.用unordered_set

349. 两个数组的交集 - 力扣（LeetCode） (leetcode-cn.com)

 1 class Solution {
 2 public:
 3     vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
 4         vector<int> ans;
 5         unordered_set<int> set;
 6         for(int i=0;i<nums1.size();i++){
 7             set.insert(nums1[i]);
 8         }
 9         for(int i=0;i<nums2.size();i++){
10             if(set.count(nums2[i])){
11                 ans.push_back(nums2[i]);
12                 set.erase(nums2[i]);
13             }
14         }
15         return ans;
16     }
17 };

View Code

3.用unordered_map实现

1. 两数之和 - 力扣（LeetCode） (leetcode-cn.com)

 1 class Solution {
 2 public:
 3     vector<int> twoSum(vector<int>& nums, int target) {
 4         unordered_map<int,int> a;//key是值，value是数组下标
 5         for(int i=0;i<nums.size();i++){
 6             if(a.count(target-nums[i])){
 7                 return{i,a[target-nums[i]]};
 8             }else{
 9                 a[nums[i]]=i;//a.insert(make_pair(nums[i],i));
10             }
11         }
12         return {};
13     }
14 };

View Code