Leetcode question brushing (5.28) hash table

1. Effective alphabetic words

242

subject ：
Given two strings s and t , Write a function to determine t Whether it is s Letter heteronym of .

Be careful ： if s and t Each character in the has the same number of occurrences , said s and t They are mutually alphabetic words .

 Input : s = "anagram", t = "nagaram"
 Output : true

 Input : s = "rat", t = "car"
 Output : false

Ideas ：
Use a length of 26 Array of represents hash table ,s The corresponding position of the middle letter in the hash table （s[i] - ‘a’） Add one ,t The middle letters are then subtracted by one , Finally, check whether the hash table is all 0, otherwise false.

note ：

When it comes to quickly determining whether an element appears in the set , Think about hashifa .

But hashifa also sacrificed space for time , Because you need to use extra arrays ,set Or is it map To store data , In order to achieve fast search .

When it comes to using collections to solve hash problems , priority of use unordered_set, Because its query and add delete efficiency is optimal , If you need the set to be ordered , Then use set, If it requires not only order but also duplicate data , Then use multiset.

python in ord() It means take ASCII value .

C++：

//  The time complexity is O(n),  Spatial complexity O(1)
class Solution {
    
public:
    bool isAnagram(string s, string t) {
    
        int record[26] = {
    0};
        for(int i = 0; i < s.size(); i++){
    
            record[s[i] - 'a']++;
        }
        for(int i = 0; i < t.size(); i++){
    
            record[t[i] - 'a']--;
        }
        for(int i = 0; i < 26; i++){
    
            if(record[i] != 0){
    
                return false;
            }
        }
        return true;
    }
};

Python：

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        record = [0] * 26
        for i in range(len(s)):
            record[ord(s[i]) - ord("a")] += 1
        for i in range(len(t)):
            record[ord(t[i]) - ord("a")] -= 1
        for i in range(26):
            if record[i] != 0:
                return False
                break
        return True

2. Intersection of two arrays

349

subject ：
Given two arrays nums1 and nums2 , return Their intersection . Every element in the output must be only Of . We can Regardless of the order of the output results .

 Input ：nums1 = [1,2,2,1], nums2 = [2,2]
 Output ：[2]

 Input ：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
 Output ：[9,4]
 explain ：[4,9]  It is also passable 

Ideas ：
C++：

use unordered_set Realization
Be careful ： Use it directly set Not only does it take up more space than arrays , And it's slower than arrays （ So can we use arrays or try to use arrays ）

Python：
Two arrays become two sets , Intersection of sets , Then revert to array （list）

note ：
C++：

1. for ( : ) For traversing arrays
2. unordered_set::find() The function is C++ STL Built in functions in , Used to search for elements in containers .
   Returns the iterator that found the element , Otherwise, it points back to unordered_set Iterator at the end .

Python：
& ： Intersection of sets

C++：

class Solution {
    
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    
        unordered_set<int> result_set;
        unordered_set<int> nums_set(nums1.begin(), nums1.end());
        for (int num : nums2) {
    
        	//  Commonly used find and end Combine to judge num_set Whether contains num
        	//  If nums_set contains nums2 Insert it into result_set in 
        	//  here nums_set yes nums1 Converted （ duplicate removal ）
            if (nums_set.find(num) != nums_set.end()){
    
                result_set.insert(num);
            }
        }
        return vector<int> (result_set.begin(), result_set.end());
    }
};

Python：

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1) & set(nums2))