哈希表

常见的三种哈希结构

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

• 数组
• set （集合）
• map(映射)

这里数组就没啥可说的了，我们来看一下 set。

在 C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：

集合	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::set	红黑树	有序	否	否	O(log n)	O(log n)
std::multiset	红黑树	有序	是	否	O(log n)	O(log n)
std::unordered_set	哈希表	无序	否	否	O(1)	O(1)

std::unordered_set 底层实现为哈希表，std::set 和 std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以 key 值是有序的，但 key 不可以修改，改动 key 值会导致整棵树的错乱，所以只能删除和增加。

映射	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::map	红黑树	key 有序	key 不可重复	key 不可修改	O(log n)	O(log n)
std::multimap	红黑树	key 有序	key 可重复	key 不可修改	O(log n)	O(log n)
std::unordered_map	哈希表	key 无序	key 不可重复	key 不可修改	O(1)	O(1)

std::unordered_map 底层实现为哈希表，std::map 和 std::multimap 的底层实现是红黑树。同理，std::map 和 std::multimap 的 key 也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。

当我们要使用集合来解决哈希问题的时候，优先使用 unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用 set，如果要求不仅有序还要有重复数据的话，那么就用 multiset。

那么再来看一下 map ，在 map 是一个 key value 的数据结构，map 中，对 key 是有限制，对 value 没有限制的，因为 key 的存储方式使用红黑树实现的。

其他语言例如：java 里的 HashMap ，TreeMap 都是一样的原理。可以灵活贯通。

虽然 std::set 和 std::multiset 的底层实现基于红黑树而非哈希表，它们通过红黑树来索引和存储数据。不过给我们的使用方式，还是哈希法的使用方式，即依靠键（key）来访问值（value）。所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法。std::map 也是一样的道理。

242.有效的字母异位词

力扣题目链接

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

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

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

说明: 你可以假设字符串只包含小写字母。

解答：

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()) return false;
        int[] str1 = new int[128];
        int[] str2 = new int[128];
        for(int i = 0;i < s.length();i++){
            str1[s.charAt(i)]++;
            str2[t.charAt(i)]++;
        }
        if(Arrays.equals(str1,str2)) return true;
        else return false;
    }
}

49.字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

解答：

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map= new HashMap<>();
        for(String s : strs){
            char[] ss = s.toCharArray();
            Arrays.sort(ss);
            String key = new String(ss);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(s);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());

    }
}

438. 找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的

异位词

的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

解答：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int[] str1 = new int[128];
        for(char c : p.toCharArray()) str1[c]++;

        int left = 0,right = 0;
        while(right < s.length()){
            str1[s.charAt(right)]--;
            while(str1[s.charAt(right)] < 0){
                str1[s.charAt(left)]++;
                left++;
            }
            if(right - left + 1 == p.length()) res.add(left);
            right++;
        }
        return res;
    }
}

349. 两个数组的交集

力扣题目链接

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

说明： 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。

解答：

import java.util.Set;
import java.util.HashSet;

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

350. 两个数组的交集 II

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

解答：

import java.util.Map;
import java.util.HashMap;

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) return new int[0];
        Map<Integer, Integer> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < nums1.length; i++){
            map.put(nums1[i], map.getOrDefault(nums1[i], 0) + 1);
        }

        for(int i = 0; i < nums2.length; i++){
            if(map.getOrDefault(nums2[i], 0) > 0){
                list.add(nums2[i]);
                map.put(nums2[i], map.get(nums2[i]) - 1);
            }
        }
        int[] arr = new int[list.size()];
        int j = 0;
        for(int i : list) arr[j++] = i;
        return arr;
    }
}

第 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

解答：

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> set1 = new HashSet<>();
        while(n != 1 && !set1.contains(n)){
            set1.add(n);
            n = getNextNumber(n);
        }
        return n == 1;
    }

    private int getNextNumber(int n) {

        int temp = n%10;
        int sum = temp*temp;
        while(n/10 > 0){
            n = n / 10;
            temp = n%10;
            sum += temp * temp;
        }
        return sum;
    }
}

1. 两数之和

力扣题目链接

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

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

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

解答：

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

        }
        return new int[2];
    }
}

第 454 题.四数相加 II

力扣题目链接

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。

例如:

输入:

• A = [ 1, 2]
• B = [-2,-1]
• C = [-1, 2]
• D = [ 0, 2]

输出:

2

解释:

两个元组如下:

1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

解答：

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> map = new HashMap<>();
        int sum = 0;
        int cnt = 0;
        for(int i : nums1){
            for(int j : nums2){
                sum = i + j;
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }
        for(int i : nums3){
            for(int j : nums4){
                sum = 0 - i - j;
                cnt += map.getOrDefault(sum, 0);
            }
        }
        return cnt;
    }
}

383. 赎金信

力扣题目链接

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

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

解答：

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // Map<char, Integer> map =HashMap<>();
        int[] arr1 = new int[128];
        int[] arr2 = new int[128];
        for(char c : ransomNote.toCharArray()) arr1[c]--;
        for(char c : magazine.toCharArray()) arr1[c]++;
        for(int i = 0; i < arr1.length; i++){
            if(arr1[i] < 0) return false;
        }
        return true;
    }
}

第 15 题. 三数之和

力扣题目链接

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

解答：

//双指针，左端枚举，右边用双指针枚举
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();

        for(int i = 0; i < nums.length-2; i++){
            int x = nums[i];
            if(i > 0 && x == nums[i - 1]) continue;
            if(x + nums[i+1] + nums[i+2] > 0) break;
            if(x + nums[nums.length - 1] + nums[nums.length - 2] < 0) continue;
            int j = i + 1;
            int k = nums.length - 1;
            while(j < k){
                int sum = x + nums[j] + nums[k];
                if(sum > 0){
                    k--;
                } else if(sum < 0){
                    j++;
                } else{
                    list.add(List.of(x, nums[j], nums[k]));
                    for(j++;j < k && nums[j - 1] == nums[j];j++);
                    for(k--;j < k && nums[k + 1] == nums[k];k--);
                }
            }
        }
        return list;
    }
}

//哈希集合
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();

        for(int i = 0; i < nums.length - 2; i++){
            int x = nums[i];
            if(i > 0 && x == nums[i - 1]) continue;
            if(x + nums[i+1] + nums[i+2] > 0) break;
            if(x + nums[nums.length - 1] + nums[nums.length - 2] < 0) continue;

            Set<Integer> set1 = new HashSet<>();

            for(int j = i + 1; j < nums.length; j++){
                int y =nums[j];
                if(j > i + 2 && y == nums[j - 1] && y == nums[j - 2]) continue;
                int z = 0 - x - y;
                if(set1.contains(z)){
                    list.add(Arrays.asList(x, y, z));
                    set1.remove(z);
                } else{
                    set1.add(nums[j]);
                }
            }
        }
        return list;
    }
}

第 18 题. 四数之和

力扣题目链接

题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

解答：

//左右两端枚举，中间用双指针枚举
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();
        int n = nums.length;
        for(int i = 0; i < n - 3; i++){
            long x = nums[i];
            if(i > 0 && x == nums[i-1]) continue;
            if(x + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
            if(x + nums[n - 1] + nums[n - 2] + nums[n - 3] < target) continue;
            int j = i + 1;

            for(int k = n - 1; k - 1 > j; k--){
                if(k < n - 1 && nums[k] == nums[k + 1]) continue;
                if(nums[k] + x + nums[i + 1] + nums[i + 2] > target) continue;
                int m = k - 1;
                while(j < m){
                    long sum = x + nums[j] + nums[k] + nums[m];
                    if(sum > target){
                        m--;
                    } else if(sum < target){
                        j++;
                    }else{
                        list.add(Arrays.asList((int)x, nums[j], nums[m], nums[k]));
                        for(j++; j < m && nums[j] == nums[j-1]; j++);
                        for(m--; j < m && nums[m] == nums[m+1]; m--);
                    }
                }
                j = i + 1;

            }
        }
        return list;
    }
}

总结

哈希表理论基础

一般来说哈希表都是用来快速判断一个元素是否出现集合里。

对于哈希表，要知道哈希函数和哈希碰撞在哈希表中的作用。

哈希函数是把传入的 key 映射到符号表的索引上。

哈希碰撞处理有多个 key 映射到相同索引上时的情景，处理碰撞的普遍方式是拉链法和线性探测法。

接下来是常见的三种哈希结构：

• 数组
• set（集合）
• map（映射）

哈希表经典题目

数组作为哈希表

一些应用场景就是为数组量身定做的。

在242.有效的字母异位词 中，我们提到了数组就是简单的哈希表，但是数组的大小是受限的！

这道题目包含小写字母，那么使用数组来做哈希最合适不过。

在383.赎金信 中同样要求只有小写字母，那么就给我们浓浓的暗示，用数组！

本题和242.有效的字母异位词 很像，242.有效的字母异位词 是求 字符串 a 和 字符串 b 是否可以相互组成，在383.赎金信 中是求字符串 a 能否组成字符串 b，而不用管字符串 b 能不能组成字符串 a。

一些同学可能想，用数组干啥，都用 map 不就完事了。

上面两道题目用 map 确实可以，但使用 map 的空间消耗要比数组大一些，因为 map 要维护红黑树或者符号表，而且还要做哈希函数的运算。所以数组更加简单直接有效！

set 作为哈希表

在349. 两个数组的交集 中我们给出了什么时候用数组就不行了，需要用 set。

这道题目没有限制数值的大小，就无法使用数组来做哈希表了。

主要因为如下两点：

• 数组的大小是有限的，受到系统栈空间（不是数据结构的栈）的限制。
• 如果数组空间够大，但哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

所以此时一样的做映射的话，就可以使用 set 了。

关于 set，三种可用的数据结构中，std::set 和 std::multiset 底层实现都是红黑树，std::unordered_set 的底层实现是哈希， 使用 unordered_set 读写效率是最高的，本题并不需要对数据进行排序，而且还不要让数据重复，所以选择 unordered_set。

在202.快乐数 中，我们再次使用了 unordered_set 来判断一个数是否重复出现过。

map 作为哈希表

在1.两数之和 中 map 正式登场。

来说一说：使用数组和 set 来做哈希法的局限。

• 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
• set 是一个集合，里面放的元素只能是一个 key，而两数之和这道题目，不仅要判断 y 是否存在而且还要记录 y 的下标位置，因为要返回 x 和 y 的下标。所以 set 也不能用。

map 是一种<key, value>的结构，本题可以用 key 保存数值，用 value 在保存数值所在的下标。所以使用 map 最为合适。

三种 map 中 std::unordered_map 底层实现为哈希，std::map 和 std::multimap 的底层实现是红黑树。

同理，std::map 和 std::multimap 的 key 也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解），1.两数之和 中并不需要 key 有序，选择 std::unordered_map 效率更高！

在454.四数相加 中我们提到了其实需要哈希的地方都能找到 map 的身影。

本题咋眼一看好像和18. 四数之和 ，15.三数之和 差不多，其实差很多！

关键差别是本题为四个独立的数组，只要找到 A[i] + B[j] + C[k] + D[l] = 0 就可以，不用考虑重复问题，而18. 四数之和 ，15.三数之和 是一个数组（集合）里找到和为 0 的组合，可就难很多了！

用哈希法解决了两数之和，很多同学会感觉用哈希法也可以解决三数之和，四数之和。

在15.三数之和 中我给出了哈希法和双指针两个解法，大家就可以体会到，使用哈希法还是比较麻烦的。

所以 18. 四数之和，15.三数之和都推荐使用双指针法！

其他

205. 同构字符串

力扣题目链接

给定两个字符串 s 和 t，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

解答：

import java.util.*;
class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) return false;
        Map<Character, Character> map1 = new HashMap<>();
        Map<Character, Character> map2 = new HashMap<>();
        for(int i = 0; i < s.length(); i++){
            if(!map1.containsKey(s.charAt(i))){
                map1.put(s.charAt(i), t.charAt(i));
            }
            else{
                if(map1.get(s.charAt(i)) != t.charAt(i)) return false;
            }

            if(!map2.containsKey(t.charAt(i))){
                map2.put(t.charAt(i), s.charAt(i));
            }
            else{
                if(map2.get(t.charAt(i)) != s.charAt(i)) return false;
            }
        }

        return true;
    }
}

1002. 查找常用字符

力扣题目链接

给你一个字符串数组 words ，请你找出所有在 words 的每个字符串中都出现的共用字符（ 包括重复字符），并以数组形式返回。你可以按 任意顺序 返回答案。

解答：

// map
import java.util.*;
class Solution {
    public List<String> commonChars(String[] words) {
        List<String> result = new ArrayList<>();
        Map<Character, Integer> freq = new HashMap<>();
        for(char c : words[0].toCharArray()){
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }

        for (int i = 1; i < words.length; i++) {
            Map<Character, Integer> temp = new HashMap<>();
            for(char c : words[i].toCharArray()){
                if(freq.getOrDefault(c, 0) > 0){
                    temp.put(c, temp.getOrDefault(c, 0) + 1);
                    freq.put(c, freq.get(c) - 1);
                }
            }
            freq = temp;

        }
        for(char c : freq.keySet()){
            for(int i = 0; i < freq.get(c); i++){
                result.add(String.valueOf(c));
            }
        }
        return result;
    }
}

//数组
import java.util.*;
class Solution {
    public List<String> commonChars(String[] words) {
        List<String> result = new ArrayList<>();
        int[] freq = new int[26];
        for(char c : words[0].toCharArray()){
            freq[c - 'a']++;
        }

        for (int i = 1; i < words.length; i++) {
            int[] temp = new int[26];
            for(char c : words[i].toCharArray()){
                if(freq[c - 'a'] > 0){
                    temp[c - 'a']++;
                    freq[c - 'a']--;
                }
            }
            freq = temp;

        }
        for(int i = 0; i < 26; i++){
            if(freq[i] > 0){
                for(int j = 0; j < freq[i]; j++){
                    result.add(String.valueOf((char)(i + 'a')));
                }
            }
        }
        return result;
    }
}