Summary

Hash

有效的字母异位词 242. Valid Anagram 💚

两个数组的交集 349. Intersection of Two Arrays💚

快乐数 202. Happy Number💚

两数之和 1. Two Sum💚

四数相加II 454. 4Sum II🧡

赎金信 383. Ransom Note💚

补充
8.1 length/length()/size()
8.2 Array判空
8.3 HashMap Key 的唯一性

1. Hash

一般哈希表都是用来快速判断一个元素是否出现集合里。要枚举的话时间复杂度是O(n)，但如果使用哈希表的话，只需要O(1)就可以做到。

2. 有效的字母异位词 242. Valid Anagram 💚

数组就是简单哈希表，因为小写字母只有26个，所以本题可以用数组。
定义一个数组叫做record用来上记录字符串s里字符出现的次数。

需要把字符映射到数组也就是哈希表的索引下标上，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。

再遍历字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了。这样就将字符串s中字符出现的次数，统计出来了。

那看一下如何检查字符串t中是否出现了这些字符，同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作。

那么最后检查一下，record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false。

最后如果record数组所有元素都为零0，说明字符串s和t是字母异位词，return true。

时间复杂度为O(n)，空间上因为定义是的一个常量大小的辅助数组，所以空间复杂度为O(1)。

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] record = new int[26];
        for(int i = 0; i < s.length(); i++){
            record[s.charAt(i) - 'a']++;
        }
        for(int i = 0; i< t.length(); i++){
            record[t.charAt(i) - 'a']--;
        }
        for(int count: record){
            if(count != 0){
                return false;
            }
        }
        return true;
    }
}

3. 两个数组的交集 349. Intersection of Two Arrays💚

注意题目特意说明：输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的，同时可以不考虑输出结果的顺序
但是要注意，使用数组来做哈希的题目，是因为题目都限制了数值的大小。而这道题目没有限制数值的大小，就无法使用数组来做哈希表了。

而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。不要小瞧这个耗时，在数据量大的情况，差距是很明显的。

思路：把数组1中的数据全部放入set中，然后遍历数组2，判断哈希表中是否存在该元素，

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0){
            return new int[0];
        }
        HashSet<Integer> set = new HashSet<Integer>();
        HashSet<Integer> res = new HashSet<Integer>();
        for (int i = 0; i < nums1.length; i++){
            set.add(nums1[I]);
        }
        for(int i = 0; i < nums2.length; i++){
            if(set.contains(nums2[i])){
                res.add(nums2[I]);
            }
        }
        return res.stream().mapToInt(x -> x).toArray();
    }
}

⚠️：set转数组：resSet.stream().mapToInt(x -> x).toArray()

4. 快乐数 202. Happy Number💚

思路：
题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！
当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。

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

判断sum是否重复出现就可以使用unordered_set。

class Solution {
    public boolean isHappy(int n) {
        HashSet<Integer> record = new HashSet<Integer>();
        while (n != 1 && !record.contains(n)){
            record.add(n);
            n = getNextNumber(n);
        }
        return n == 1;
    }
    
    public int getNextNumber(int n){
        int res = 0;
        while(n > 0){
            int temp = n % 10;
            res += temp * temp;
            n = n/10;
        }
        return res;
    }
}

5. 两数之和 1. Two Sum💚

首先我在强调一下什么时候使用哈希法，当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。
本题呢，我就需要一个集合来存放我们遍历过的元素，然后在遍历数组的时候去询问这个集合，某元素是否遍历过，也就是是否出现在这个集合。因为本题，我们不仅要知道元素有没有遍历过，还有知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。

在遍历数组的时候，只需要向map去查询是否有和目前遍历元素比配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进map中，因为map存放的就是我们访问过的元素。

step1

step2

class Solution{
    public int[] twoSum(int[] nums, int target){
        HashMap<Integer,Integer> record = new HashMap<>();
        int[] res = new int[2];
        if(nums == null || nums.length == 0){
            return null;
        }
        for(int i = 0; i < nums.length; i++){
            int temp = target - nums[i];
                if(record.containsKey(temp)){
                    res[1] = i;
                    res[0] = record.get(temp);
                }
            record.put(nums[i],i);
        }
        return res;
    }
}
//Time O(n)

6. 四数相加II 454. 4Sum II🧡

本题是使用哈希法的经典题目，而0015.三数之和 (opens new window)，0018.四数之和 (opens new window)并不合适使用哈希法，因为三数之和和四数之和这两道题目使用哈希法在不超时的情况下做到对结果去重是很困难的，很有多细节需要处理。

而这道题目是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况，所以相对于题目18. 四数之和，题目15.三数之和，还是简单了不少！
本题解题步骤：

首先定义一个unordered_map，key放a和b两数之和，value 放a和b两数之和出现的次数。
遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中
定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
最后返回统计值 count 就可以了

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> map = new HashMap<>();
        int temp;
        int res = 0;
        //统计两个数组中的元素之和，同时统计出现的次数，放入map
        for (int i : nums1) {
            for (int j : nums2) {
                temp = i + j;
                if (map.containsKey(temp)) {
                    map.put(temp, map.get(temp) + 1);
                } else {
                    map.put(temp, 1);
                }
            }
        }
        //统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
        for (int i : nums3) {
            for (int j : nums4) {
                temp = i + j;
                if (map.containsKey(0 - temp)) {
                    res += map.get(0 - temp);
                }
            }
        }
        return res;
    }
}

⚠️：HashMap 中，key不会重复。如果重复添加的话，HashMap会自动覆盖key一样的数据，保证一个key对应一个value。所以不需要删除原来的数据

7. 赎金信 383. Ransom Note💚

跟有效的字母异位词 242. Valid Anagram，一模一样。创建数组储存字母出现次数。但本题多了一个逻辑判断，即if(ransom.length > magazine.length) return false

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] note = new int[26];
        if(ransomNote.length() > magazine.length()){
            return false;
        }

        for (int i = 0; i < magazine.length(); i++){
            note[magazine.charAt(i) - 'a']++;
        }
        for(int i = 0; i < ransomNote.length(); i++){
            note[ransomNote.charAt(i) - 'a']--;
        }
        for(int i = 0; i < note.length; i++){
            if(note[i] < 0){
                return false;
            }
        }
        return true;
    }
}
//Time : O(n)

8.补充

8.1 length/length()/size()

length 属性是针对 Java 中的数组来说的，要求数组的长度可以用其 length 属性；
length() 方法是针对字符串来说的，要求一个字符串的长度就要用到它的length()方法；
Java 中的 size() 方法是针对泛型集合说的, 如果想看这个泛型有多少个元素, 就调用此方法来查看!（List/ArrayList）

8.2 Array判空：

if(nums == null || nums.length == 0)

先判首地址是否为空，即array==null，
再判数组是否为{}，即nums.length == 0

8.3 HashMap Key 的唯一性

HashMap 中，key不会重复。如果重复添加的话，HashMap会自动覆盖key一样的数据，保证一个key对应一个value。所以不需要删除原来的数据

2022-11-02 Hash