[数据结构与算法]leetcode哈希表（哈希集合，哈希映射）

哈希表

哈希表是一种使用哈希函数组织数据，以支持快速插入和搜索的数据结构。

有两种不同类型的哈希表：哈希集合和哈希映射。

• 哈希集合是集合数据结构的实现之一，用于存储非重复值。
• 哈希映射是映射 数据结构的实现之一，用于存储(key, value)键值对。

1.原理

简单介绍下：
哈希表的关键思想是使用哈希函数将键映射到存储桶。更确切地说

• 当插入一个新的键时，哈希函数将决定该键应该分配到哪个桶中，并将该键存储在相应的桶中；
• 当想要搜索一个键时，哈希表将使用相同的哈希函数来查找对应的桶，并只在特定的桶中进行搜索

更深层次的底层原理以及如何设计哈希集合和哈希映射，可以参见哈希表底层原理分析

lc705设计哈希集合
lc706设计哈希映射

2.复杂度分析

题目&推荐列表

本文题目

推荐习题

注：排序＋双指针在有关哈希题目中经常可以达到奇效（包括后面的四数之和，四数相加，用哈希来做其实复杂度就很高了）

哈希集合的应用

哈希集是集合的实现之一，它是一种存储不重复值的数据结构；

所以可以 使用哈希集合来查重。

注意的几个点是：
1.底层数据结构是哈希表 ；2.没有带索引的方法；3.不包含重复元素。

对于哈希集合（HashSet）用法还不熟悉的可以看看这篇 HashSet基础入门

这里还是回顾一下主要方法：

0.常用解题模板

（仅供参考）

// 利用HashSet查重
boolean findDuplicates(List<T> keys) {
    // 首先创建一个哈希集合，T表示实际中的数据类型
    Set<T> hashset = new HashSet<>();
    // 对给定的集合或者列表进行遍历
    for (T key : keys) {
        if (hashset.contains(key)) {
            return true;
        }
        hashset.add(key);
    }
    return false;
}

1.lc217 存在重复元素

力扣217链接

描述：

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false

示例：

输入：nums = [1,2,3,1]
输出：true
输入：nums = [1,2,3,4]
输出：false

Solution：

典型的查重，运用Set的去重性（与模板高度相似）

public boolean containsDuplicate(int[] nums) {
         Set<Integer> set = new HashSet<>();

         for(int num:nums)
         {
             if(set.contains(num))
                return true;
             set.add(num);
         }
         return false;
    }

2.lc136 只出现一次的数字

力扣136链接

描述：

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

示例：

输入: [4,1,2,1,2]
输出: 4

Solution 1: 哈希集合

public static int singleNumber1(int[] nums) {
       // 使用集合存储数字
        Set<Integer> set = new HashSet<>();
       // 遍历数组中的每个数字
        for (int num:nums) {
            // 如果集合中没有该数字，则将该数字加入集合
            if (!set.contains(num))
                set.add(num);
            // 如果集合中已经有该数字，则将该数字从集合中删除  
            else
                set.remove(num);
        }
       // 最后剩下的数字就是只出现一次的数字
       return set.iterator().next();
}

Solution2：哈希映射
注意，和次数相关的题目第一反应要想到哈希映射！

public static int singleNumber2(int[] nums) {
       // 使用哈希表存储每个数字和该数字出现的次数
		Map<Integer, Integer> map = new HashMap<>();
        
        // 遍历数组即可得到每个数字出现的次数，并更新哈希表
        for (int num : nums) {
            int count = 1;
            if (map.containsKey(num)) {
                count++;
                map.put(num, count);
                // 可以直接用map.put(num,map.getordefault(x,0)+1)
            }
            map.put(num, count);
        }
        // 最后遍历哈希表，得到只出现一次的数字
        for (Integer key : map.keySet()) {
            if (map.get(key) == 1)
                return key;
        }
        return -1;

Solution 3：位运算（官方）
时间复杂度O(n)，空间复杂度O(1)

 public static int singleNumber3(int[] nums) {
        // 相同的数异或为0，异或具有交换律
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            res = res ^ nums[i];
        }
        return res;
    }

3.快乐数

力扣202链接

描述：

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

示例：

输入：n = 19
输出：true
输入：n = 2
输出：false

Solution :
哈希集合，判断每一次新数的总和是否重复

public boolean isHappy(int n) {
        Set<Integer> record = new HashSet<>();
        // 利用 HashSet 的去重性
        while (n != 1 && !record.contains(n)) {
            record.add(n);
            n = getNextNumber(n);
        }
        return n == 1;
    }
// 先去求下一个新数
private int getNextNumber(int n) {
        int res = 0;
        while (n > 0) {
            int temp = n % 10;
            res += temp * temp;
            n = n / 10;
        }
        return res;
    }

哈希映射的应用

使用哈希映射的第一个场景是，我们需要更多的信息，而不仅仅是键。然后通过哈希映射建立key与value之间的映射关系。

场景2就是按键聚合所有信息，在遇到现有键时要确定好策略。

对HashMap主要方法还不熟悉的可以参考这篇文章，HashMap基础入门,有对方法的解释和方法运用的示例。

0.常用解题模板

（仅供参考）

场景1：提供更多信息

ReturnType aggregateByKey_hashmap(List<Type>& keys) {
    // Replace Type and InfoType with actual type of your key and value
    Map<Type, InfoType> hashmap = new HashMap<>();
    for (Type key : keys) {
        if (hashmap.containsKey(key)) {
            if (hashmap.get(key) satisfies the requirement) {
                return needed_information;
            }
        }
        // Value can be any information you needed (e.g. index)
        hashmap.put(key, value);    
    }
    return needed_information;
}

场景2：按键聚合

ReturnType aggregateByKey_hashmap(List<Type>& keys) {
    // Replace Type and InfoType with actual type of your key and value
    Map<Type, InfoType> hashmap = new HashMap<>();
    for (Type key : keys) {
        if (hashmap.containsKey(key)) {
            hashmap.put(key, updated_information);
        }
        // Value can be any information you needed (e.g. index)
        hashmap.put(key, value);    
    }
    return needed_information;
}

1. lc1 两数之和

力扣1链接

描述：

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

示例：

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

Solution：

public int[] twoSum(int[] nums, int target) {
         // 创建一个HashMap
        Map<Integer,Integer> map  = new HashMap<>();
        // 创建一个数组，用来存储结果的两个下标
        int[] res = new int[2];

        for(int i=0;i<nums.length;i++)
        {
            // tmp的含义是当前的整数所需匹配的数字，如扫描到2需要的是7（9-2）
            int tmp = target-nums[i];
            
            // 判断hashmap中是否存在tmp的key
            if(map.containsKey(tmp))
            {
            /*存在这个值为tmp的key就说明此时的i肯定是其中一个索引，
            另一个索引是以tmp为key的value值*/
                res[0]=i;
                res[1]=map.get(tmp);
            }
            // 表示不存在这样的key，所以将当前数字和其下标添加到map中
            map.put(nums[i],i);
        }
        return res;
    }

2. lc387 字符串中的第一个唯一字符

力扣387链接

描述：

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1

示例：

输入: s = “loveleetcode”
输出: 2
输入: s = “aabb”
输出: -1

Solution1：哈希映射
使用哈希表存储频数。先用map存储字符出现的次数；然后遍历string,如果在map中找到了次数为1的时候就返回就返回对应的下标

class Solution {
    public int firstUniqChar(String s) {
        Map<Character, Integer> frequency = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < s.length(); ++i) {
            if (frequency.get(s.charAt(i)) == 1) {
                return i;
            }
        }
        return -1;
    }
}

Solution2：数组
数组实现哈希映射（时间上要快很多）

public static int firstUniqChar(String s) {
        int[] a = new int[26];

        for(int i=0;i<s.length();i++)
        {
            char chs = s.charAt(i);
            a[chs-'a'] ++;
        }
        for(int i=0;i<s.length();i++)
        {
            char chs = s.charAt(i);
            if(a[chs-'a']==1)
                return i;
        }
        return -1;

3. lc350 两个数组的交集II

力扣350链接

（有II肯定有I，可以先做I，lc349 两个数组的交集）

描述：

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

示例：

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

Solution：
哈希映射

在这里插入代码片

4. lc219 存在重复元素II

力扣219链接

描述：

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false

示例：

输入：nums = [1,2,3,1], k = 3
输出：true
输入：nums = [1,2,3,1,2,3], k = 2
输出：false

Solution:

public boolean containsNearbyDuplicate(int[] nums, int k) {
     Map<Integer,Integer> map = new HashMap<>();

      for(int i=0;i<nums.length;i++)
      {
          int tmp = nums[i];
          // 判断当前tmp是否存在与hashmap中，且要满足当前索引与之前索引差值不大于k
          if(map.containsKey(tmp) && i-map.get(tmp)<=k) {
             return true;
          }
          //如果不满足要求，就把当前元素存入hashmap中
          map.put(tmp,i);
      }
      return false;

参考链接：
https://leetcode.cn/leetbook/read/hash-table/