哈希表理论基础及经典算法题实战

349. 两个数组的交集

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

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

输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的，同时可以不考虑输出结果的顺序。

这个题增添了数值范围：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

题目限制了数值大小，所以可以采用数组求解。

如果题目没有限制数值的大小，就无法使用数组来做哈希表了。因为使用数组来做哈希的题目，是因为题目都限制了数值的大小。**而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。**这时候用 Set 来解决。

但是不能什么哈希问题都用 Set，因为直接使用 Set 不仅占用空间比数组大，而且速度要比数组慢，Set 把数值映射到 key 上都要做 hash 计算的。

使用数组求解：

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // 1002 是因为比最大元素值 1000 多 2，预留冗余避免越界
        int[] hash1 = new int[1002];
        int[] hash2 = new int[1002];
        // 遍历数组 nums1 的每一个元素，计数在 nums1 中出现的次数
        for (int i : nums1) hash1[i]++;
        for (int i : nums2) hash2[i]++;
        // 创建动态整数列表，收集两个数组的交集元素
        java.util.List<Integer> resList = new java.util.ArrayList<>();
        for (int i = 0; i < 1002; i++) {
            // 交集元素 +1
            if (hash1[i] > 0 && hash2[i] > 0) resList.add(i);
        }
        // 将存储交集元素的 List 集合（resList），转换为最终需要返回的 int 类型数组
        int[] res = new int[resList.size()];
        for (int j = 0; j < resList.size(); j++) {
            res[j] = resList.get(j);
        }
        return res;
    }
}

写法 2：用 HashSet 去重，再 retainAll 取交集，不受数据范围限制

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // 注意和上面对比，遍历的逻辑一样，只是换成 set
        java.util.Set<Integer> set1 = new java.util.HashSet<>();
        java.util.Set<Integer> set2 = new java.util.HashSet<>();
        for (int n : nums1) set1.add(n);
        for (int n : nums2) set2.add(n);
        // 保留 set1 中与 set2 共有的元素，删除 set1 中独有的元素
        set1.retainAll(set2);
        // 取交集
        // 创建结果数组
        int[] res = new int[set1.size()];
        // 遍历 set1 中的交集元素，通过一个计数变量 i 把元素依次存入 res 数组
        int i = 0;
        for (int n : set1) res[i++] = n;
        return res;
    }
}

202. 快乐数

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

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

如果 n 是快乐数就返回 True；不是，则返回 False。

示例： 输入：19。输出：true 解释：1^2 + 9^2 = 82, 8^2 + 2^2 = 68, 6^2 + 8^2 = 100, 1^2 + 0^2 + 0^2 = 1

题目中说了会无限循环，那么也就是说求和的过程中，sum 会重复出现，这对解题很重要！

这道题目使用哈希法，来判断这个 sum 是否重复出现，如果重复了就是 return false，否则一直找到 sum 为 1 为止。还有一个难点就是求和的过程，如果对取数值各个位上的单数操作不熟悉的话，做这道题也会比较艰难。

class Solution {
    public boolean isHappy(int n) {
        java.util.Set<Integer> record = new java.util.HashSet<>();
        // 如果当前数 n 已存在于 record（存储过的中间结果），说明进入无限循环（永远到不了 1），终止循环
        while (n != 1 && !record.contains(n)) {
            record.add(n);
            n = getNextNumber(n);
        }
        return n == 1;
    }

    private int getNextNumber(int n) {
        int res = 0;
        // 计算一个整数 n 所有位上数字的平方和
        while (n > 0) {
            int temp = n % 10; // 个位
            res += temp * temp; // 个位平方和
            n = n / 10; // 去掉个位，接下来循环算十位，直到变成 0
        }
        return res;
    }
}

1. 两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

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

当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

本题，不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key-value 结构来存放，key 来存元素，value 来存下标，那么使用 Map 正合适。

遍历当前元素，并在 map 中寻找是否有匹配的 key，计算互补元素 temp，判断哈希表 map 中是否存在互补元素 temp，存在就找到了答案。将当前元素的下标 i 存入 res 的第二个位置，获取互补元素 temp 在数组中的下标，并存入 res 的第一个位置。

res[1] 存储后遍历到的元素的下标（即 i），因为 i 是当前循环的索引，比哈希表中存储的 j（map.get(temp)）更大。

// 使用哈希表
public int[] twoSum(int[] nums, int target) {
    int[] res = new int[2]; // 结果数组
    if (nums == null || nums.length == 0) {
        return res;
    }
    java.util.Map<Integer, Integer> map = new java.util.HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        // 遍历当前元素，并在 map 中寻找是否有匹配的 key
        // 计算互补元素 temp
        int temp = target - nums[i];
        // 判断哈希表 map 中是否存在互补元素 temp，存在就找到了答案
        if (map.containsKey(temp)) {
            // 将当前元素的下标 i 存入 res 的第二个位置
            res[1] = i;
            // 获取互补元素 temp 在数组中的下标，并存入 res 的第一个位置
            res[0] = map.get(temp);
            break;
        }
        // 如果没找到匹配对，就把访问过的元素和下标加入到 map 中
        map.put(nums[i], i);
    }
    return res;
}

如果题目没保证有序，就不能用双指针。如果想用双指针需要先排序，数组有序，就应该想到双指针技巧。