当我们遇到要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。
如果题目遇到需要判断一个元素是否出现过的场景应该第一时间想到哈希法。

1. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:
输入: s = “anagram”, t = “nagaram”
输出: true

示例 2:
输入: s = “rat”, t = “car”
输出: false

# python
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        record = [0] * 26
        for i in s:
            record[ord(i) - ord('a')] += 1	# ord()函数一一个字符（长度为1的字符串）为参数，返回对应ASCII数值。
        for j in t:
            record[ord(j) - ord('a')] -= 1
        for k in range(26):
            if record[k] != 0:
                return False
        return True

# Java
class Solution {
    public boolean isAnagram(String s, String t) {
        int[] record = new int[26];
        for (char c : s.toCharArray()) {
            record[c - 'a']++;
        }
        for (char c : t.toCharArray()) {
            record[c - 'a']--;
        }
        for (int i : record) {
            if (i != 0) {
                return false;
            }
        }
        return true;
    }
}

2. 两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。

示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]

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

# Java
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
            return new int[0];
        }
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();
        for (int i : nums1) {
            set1.add(i);
        }
        for (int j : nums2) {
            if (set1.contains(j)) {
                resSet.add(j);
            }
        }
        int index = 0;
        int[] resArr = new int[resSet.size()];
        for (int k : resSet) {
            resArr[index++] = k;
        }
        return resArr;
    }
}

3. 两个数组的交集II

给定两个数组，编写一个函数来计算它们的交集。

示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

说明：
输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
我们可以不考虑输出结果的顺序。

# python
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        m = collections.Counter()
        for i in nums1:
            m[i] += 1
        resArr = []
        for j in nums2:
            count = m.get(j, 0)
            if count > 0:
                resArr.append(j)
                m[j] -= 1
        return resArr
# Java
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i : nums1) {
            int count = map.getOrDefault(i, 0) + 1;
            map.put(i, count);
        }
        int index = 0;
        int len = nums1.length > nums2.length ? nums1.length : nums2.length;
        int[] resArr = new int[len];
        for (int j : nums2) {
            int count = map.getOrDefault(j, 0);
            if (count-- > 0) {
                resArr[index++] = j;
                map.put(j, count);
            }
        }
        return Arrays.copyOfRange(resArr, 0, index);
    }
}

4. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。

示例 1：
输入：19
输出：true
解释：
1 2 + 9 2 = 82 8 2 + 2 2 = 68 6 2 + 8 2 = 100 1 2 + 0 2 + 0 2 = 1 1^{2}+9^{2}=82 \\ 8^{2} + 2^{2} = 68 \\ 6^{2} + 8^{2} = 100 \\ 1^{2}+0^{2}+0^{2}=1 12+92=8282+22=6862+82=10012+02+02=1

示例 2：
输入：n = 2
输出：false

这道题目可以使用哈希法，来判断这个sum是否重复出现，如果重复了就return false， 否则一直找到sum为1为止。

# python
class Solution:
    def isHappy(self, n: int) -> bool:
        def caculate_sum(n):
            sum = 0
            while(n):   
                tmp = n % 10
                sum += tmp**2
                n = n // 10
            return sum
        record = set()
        while(True):
            record.add(n)
            n = caculate_sum(n)
            if n == 1:
                return True
            if n in record:
                return False

# Java
class Solution {
    private int calculateSum(int n) {
        int sum = 0;
        while (n != 0) {
            int tmp = n % 10;
            sum += tmp*tmp;
            n = n / 10;
        }
        return sum;
    }
    public boolean isHappy(int n) {
        Set record = new HashSet();
        while (true) {
            record.add(n);
            n = calculateSum(n);
            if (n == 1) {
                return true;
            }
            if (record.contains(n)) {
                return false;
            }
        }
    }
}

5. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]

map是一种key value的存储结构，可以用key保存数值，用value在保存数值所在的下表。

# python
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        record = dict()
        for i, n in enumerate(nums):
            if target - n not in record:
                record[n] = i
            else:
                return [record[target - n], i]

# Java
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> record = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (!record.containsKey(target - nums[i])) {
                record.put(nums[i], i);
            }else{
                return new int[]{record.get(target - nums[i]), i};
            }
        }
        return new int[2];
    }
}

6. 四数相加II

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释： 两个元组如下：

1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

# python
class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        record = dict()
        for i in nums1:
            for j in nums2:
                tmp = i + j
                if tmp in record:
                    record[tmp] += 1
                else:
                    record[tmp] = 1
        res = 0
        for i in nums3:
            for j in nums4:
                key = -i - j
                if key in record:
                    res += record[key]
        return res

# Java
class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> record = new HashMap<>();
        int tmp;
        for (int i : nums1) {
            for (int j : nums2) {
                tmp = i + j;
                if (record.containsKey(tmp)) {
                    record.put(tmp, record.get(tmp) + 1);
                } else {
                    record.put(tmp, 1);
                }
            }
        }
        int res = 0;
        int key;
        for (int i : nums3) {
            for (int j : nums4) {
                key = - i - j;
                if (record.containsKey(key)) {
                    res += record.get(key);
                }
            }
        }
        return res;
    }
}

7. 赎金信

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

示例 1：
输入：ransomNote = “a”, magazine = “b”
输出：false

示例 2：
输入：ransomNote = “aa”, magazine = “ab”
输出：false

示例 3：
输入：ransomNote = “aa”, magazine = “aab”
输出：true

因为题目所只有小写字母，可以用一个长度为26的数组还记录magazine里字母出现的次数。在本题的情况下，使用map的空间消耗要比数组大一些的，因为map要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！数据量大的话就能体现出来差别了。 所以数组更加简单直接有效！

# python
class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        arr = [0] * 26
        for x in magazine:
            arr[ord(x) - ord('a')] += 1
        for y in ransomNote:
            if (arr[ord(y) - ord('a')] > 0):
                arr[ord(y) - ord('a')] -= 1
            else:
                return False
        return True

# Java
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        char[] ransomNoteArr = ransomNote.toCharArray();
        char[] magazineArr = magazine.toCharArray();
        int[] arr = new int[26];
        for (char i : magazineArr) {
            arr[i - 'a'] += 1;
        }
        for (char j : ransomNoteArr) {
            if (arr[j - 'a'] > 0) {
                arr[j - 'a'] -= 1;
            } else {
                return false;
            }
        }
        return true;
    }
}