LeetCode哈希表（哈希集合，哈希映射）_leetcode 字符串哈希

哈希表

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

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

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

1.原理

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

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

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

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

2.复杂度分析

典型的空间换时间，查找的时间复杂度是O(1），空间复杂度是O(n）

题目&推荐列表

本文题目

推荐习题

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

哈希集合的应用

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

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

注意的几个点是：
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
2
3
4
5
6
7
8
9
10
11
12
13

1.lc217 存在重复元素

力扣217链接

描述：

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

示例：

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

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;
    }
1
2
3
4
5
6
7
8
9
10
11

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();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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;
    }
1
2
3
4
5
6
7
8

3.快乐数

力扣202链接

描述：

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

示例：

输入：n = 19 输出：true

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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

哈希映射的应用

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

对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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

场景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
2
3
4
5
6
7
8
9
10
11
12

1. lc1 两数之和

力扣1链接

描述：

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

示例：

输入：nums = [2,7,11,15], target = 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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

力扣387链接

描述：给定一个字符串 s ，找到它的第一个不重复的字符，并返回它的索引 。不存在，返回 -1
示例：输入: s = “loveleetcode” 输出: 2

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3. lc350 两个数组的交集II

力扣350链接

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

描述：

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

示例：

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

Solution：
哈希映射

在这里插入代码片
1

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

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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

5.lc13 罗马数字转整数

描述：给定一个罗马数字，将其转换成整数。
示例：输入: s = “III” 输出: 3 输入: s = “IX” 输出: 9

Solution:
用一个哈希表建立映射。然后遍历给定的字符串，判断左右罗马数字的大小，如果左边的比右边的小，就减去这个数，反之就加上。

 public int romanToInt(String s) {
        Map<Character,Integer> helper = new HashMap<>();

        helper.put('I',1);
        helper.put('V',5);
        helper.put('X',10);
        helper.put('L',50);
        helper.put('C',100);
        helper.put('D',500);
        helper.put('M',1000);

        int len = s.length();
        int value=0;  // 记录最后的整数

        for(int i=0;i<len;i++)
        {
            int num = helper.get(s.charAt(i)); //获取罗马数字代表的整数
            
            // 判断是加还是减
            if(i<len-1 && num<helper.get(s.charAt(i+1))) 
                value -= num;
            else
                value += num;
        }
        return value;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

时间复杂度：O(n)，其中 n 是字符串 s 的长度。空间复杂度：O(1)

6. lc1207 独一无二的出现次数

力扣1207链接

描述：给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。
如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。
输入：arr = [1,2,2,1,1,3] 输出：true

Solution：
看到次数，想到哈希法。。。

（本题第一反应是用哈希映射，如果想要时间效率更高，应该采取数组来进行哈希映射）

public boolean uniqueOccurrences(int[] arr) {
        HashMap<Integer,Integer> map = new HashMap<>();

        for(int num:arr)
        {
            map.put(num,map.getOrDefault(num,0)+1);
        }

      Set<Integer> set = new HashSet<>();
      for(int value:map.values())
      {
            if(set.contains(value))
              return false;
            else
              set.add(value);
      }
        return true;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

7. lc1365 有多少小于当前数字的数字

力扣1365链接

描述：

给你一个数组 nums，对其中每个元素 nums[i],请你统计数组中比它小的所有数字的数目
输入：nums = [8,1,2,2,3] 输出：[4,0,1,1,3]

solution：
第一眼，真想暴力，两层for直接跑路~

冷静一下，仔细想想，还得是哈希（先排序后哈希，哈希用来做数值和下标的映射）

 public int[] smallerNumbersThanCurrent(int[] nums) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int[] res = Arrays.copyOf(nums,nums.length);
        Arrays.sort(res);

        for(int i=0;i<nums.length;i++)
        {
            if(!map.containsKey(res[i]))
            {
                map.put(res[i],i);
            }
        }
        for(int i=0;i<res.length;i++)
        {
            res[i] = map.get(nums[i]);

        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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