05、第三章 哈希表part01

本节内容

  • 哈希表理论基础 
  • 242.有效的字母异位词 
  • 349. 两个数组的交集 
  • 202. 快乐数
  • 1. 两数之和

哈希表理论基础※

建议：大家要了解哈希表的内部实现原理，哈希函数，哈希碰撞，以及常见哈希表的区别，数组，set 和map。  

什么时候想到用哈希法，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。  这句话很重要，大家在做哈希表题目都要思考这句话。 

文章讲解： https://programmercarl.com/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

个人博客相关内容：
数组与集合： https://www.yuanql.top/2023/01/11/03_java%E5%9F%BA%E7%A1%80%E7%BC%96%E7%A8%8B/11_Java%E9%9B%86%E5%90%88/%E6%95%B0%E7%BB%84%E4%B8%8E%E9%9B%86%E5%90%88/
Collection接口： https://www.yuanql.top/2023/01/11/03_java%E5%9F%BA%E7%A1%80%E7%BC%96%E7%A8%8B/11_Java%E9%9B%86%E5%90%88/Collection%E6%8E%A5%E5%8F%A3/
Iterator接口与foreach循环： https://www.yuanql.top/2023/01/11/03_java%E5%9F%BA%E7%A1%80%E7%BC%96%E7%A8%8B/11_Java%E9%9B%86%E5%90%88/Iterator%E6%8E%A5%E5%8F%A3%E4%B8%8Eforeach%E5%BE%AA%E7%8E%AF/
Collection子接口：List接口： https://www.yuanql.top/2023/01/11/03_java%E5%9F%BA%E7%A1%80%E7%BC%96%E7%A8%8B/11_Java%E9%9B%86%E5%90%88/Collection%E5%AD%90%E6%8E%A5%E5%8F%A3%EF%BC%9AList%E6%8E%A5%E5%8F%A3/
Collection子接口：Set接口： https://www.yuanql.top/2023/01/11/03_java%E5%9F%BA%E7%A1%80%E7%BC%96%E7%A8%8B/11_Java%E9%9B%86%E5%90%88/Collection%E5%AD%90%E6%8E%A5%E5%8F%A3%EF%BC%9ASet%E6%8E%A5%E5%8F%A3/
Map接口： https://www.yuanql.top/2023/01/11/03_java%E5%9F%BA%E7%A1%80%E7%BC%96%E7%A8%8B/11_Java%E9%9B%86%E5%90%88/Map%E6%8E%A5%E5%8F%A3/
Collections工具类的使用： https://www.yuanql.top/2023/01/11/03_java%E5%9F%BA%E7%A1%80%E7%BC%96%E7%A8%8B/11_Java%E9%9B%86%E5%90%88/Collections%E5%B7%A5%E5%85%B7%E7%B1%BB%E7%9A%84%E4%BD%BF%E7%94%A8/

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
27
|----Collection接口：单列集合，用来存储一个一个的对象
	|----List接口：存储有序的、可重复的数据。  -->“动态”数组
		|----ArrayList、LinkedList、Vector
		|----ArrayList：作为List接口的主要实现类；线程不安全的，效率高；底层使用Object[] elementData存储
		|----LinkedList：对于频繁的插入、删除操作，使用此类效率比ArrayList高；底层使用双向链表存储
		|----Vector：作为List接口的古老实现类；线程安全的，效率低；底层使用Object[] elementData存储

	|----Set接口：存储无序的、不可重复的数据   -->高中讲的“集合”
		|----HashSet、LinkedHashSet、TreeSet
		|----HashSet：作为Set接口的主要实现类；线程不安全的；可以存储null值  
			|----LinkedHashSet：作为HashSet的子类；遍历其内部数据时，可以按照添加的顺序遍历  
			在添加数据的同时，每个数据还维护了两个引用，记录此数据前一个数据和后一个数据。  
			对于频繁的遍历操作，LinkedHashSet效率高于HashSet.  
			|----TreeSet：可以照添加对象的指定属性，进行排序。

|----Map:双列数据，存储key-value对的数据   ---类似于高中的函数：y = f(x)
	|----HashMap:作为Map的主要实现类；线程不安全的，效率高；存储null的key和value
			|----LinkedHashMap:保证在遍历map元素时，可以照添加的顺序实现遍历。
				原因：在原的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。
				对于频繁的遍历操作，此类执行效率高于HashMap。
	|----TreeMap:保证照添加的key-value对进行排序，实现排序遍历。此时考虑key的自然排序或定制排序
			底层使用红黑树
	|----Hashtable:作为古老的实现类；线程安全的，效率低；不能存储null的key和value
		|----Properties:常用来处理配置文件。key和value都是String类型

	HashMap的底层：数组+链表  （jdk7及之前)
				  数组+链表+红黑树 （jdk 8)

242.有效的字母异位词※

建议： 这道题目，大家可以感受到 数组 用来做哈希表 给我们带来的遍历之处。

题目链接： https://leetcode.cn/problems/valid-anagram/
文章讲解： https://programmercarl.com/0242.%E6%9C%89%E6%95%88%E7%9A%84%E5%AD%97%E6%AF%8D%E5%BC%82%E4%BD%8D%E8%AF%8D.html

https://www.yuanql.top/2023/06/12/02_leetcode/242.%20%E6%9C%89%E6%95%88%E7%9A%84%E5%AD%97%E6%AF%8D%E5%BC%82%E4%BD%8D%E8%AF%8D/

题目分析

先遍历字符串 s 中的所有字符，将字符放入到哈希表中，没遇到一次此字符，进行加1操作。
然后遍历字符串t中的所有字符，每遇到一次此字符，对哈希表中的相关数据进行减1操作。当当前数值减为0的时候，将哈希表中的相关数据移除，最后可以根据哈希表的尺寸来判断是否为异位词了。

方案一

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
class Solution {
    public boolean isAnagram(String s, String t) {
        HashMap<Character, Integer> hashMap = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            hashMap.put(s.charAt(i), hashMap.getOrDefault(s.charAt(i), 0) + 1);
        }

        for (int i = 0; i < t.length(); i++) {
            if (hashMap.containsKey(t.charAt(i))) {
                hashMap.put(t.charAt(i), hashMap.get(t.charAt(i)) - 1);
                if (hashMap.get(t.charAt(i)) == 0){
                    hashMap.remove(t.charAt(i));
                }
            } else {
                return false;
            }
        }

        if (hashMap.size() != 0) {
            return false;
        }
        return true;
    }
}

结果

解答成功:
执行耗时:17 ms,击败了10.95% 的Java用户
内存消耗:42.5 MB,击败了20.87% 的Java用户

分析

时间复杂度：
O( n + m )

空间复杂度：
O( 1 ) 虽然是hashmap，但是字符串中只可能有26个字母，所以复杂度是1

代码随想录

https://programmercarl.com/0242.%E6%9C%89%E6%95%88%E7%9A%84%E5%AD%97%E6%AF%8D%E5%BC%82%E4%BD%8D%E8%AF%8D.html#_242-%E6%9C%89%E6%95%88%E7%9A%84%E5%AD%97%E6%AF%8D%E5%BC%82%E4%BD%8D%E8%AF%8D

需要定义一个多大的数组呢，定一个数组叫做record，大小为26 就可以了，初始化为0，因为字符a到字符z的ASCII也是26个连续的数值。

为了方便举例，判断一下字符串s= “aee”, t = “eae”。

操作动画如下：

定义一个数组叫做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)。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 242. 有效的字母异位词 字典解法
 * 时间复杂度O(m+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']++;     // 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
        }

        for (int i = 0; i < t.length(); i++) {
            record[t.charAt(i) - 'a']--;
        }
        
        for (int count: record) {
            if (count != 0) {               // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
                return false;
            }
        }
        return true;                        // record数组所有元素都为零0，说明字符串s和t是字母异位词
    }
}

349. 两个数组的交集※

建议：本题就开始考虑 什么时候用set 什么时候用数组，本题其实是使用set的好题，但是后来力扣改了题目描述和 测试用例，添加了 0 <= nums1[i], nums2[i] <= 1000 条件，所以使用数组也可以了，不过建议大家忽略这个条件。 尝试去使用set。

题目链接： https://leetcode.cn/problems/intersection-of-two-arrays/
文章讲解： https://programmercarl.com/0349.%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%BB%84%E7%9A%84%E4%BA%A4%E9%9B%86.html

https://www.yuanql.top/2023/06/12/02_leetcode/349.%20%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%BB%84%E7%9A%84%E4%BA%A4%E9%9B%86/

题目分析

循环判断，将数组放入到hashSet中。
首先对 nums1 进行循环遍历，遍历每一个数值，然后将其放入到 HashSet 中，使用 add() 方法添加，如果 HashSet中不存在，则添加成功并返回 true ；如果已经存在，则不会再向内进行添加，并返回 false。
然后对nums2 进行循环遍历，如果再HashMap 中存在向的key，则向结果的list 中添加有关数据，并删除在 HashSet中 的此个key。
循环完毕后，list数组中所存储的数据就是需要返回的数据，最后需要将其转为 int[] 的类型

方案一

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
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> hashSet = new HashSet<>();
       List<Integer> list = new ArrayList<>();

        for (int i: nums1) { //
            hashSet.add(i);
        }

        for (int i : nums2) {
            if (hashSet.contains(i)) {
                list.add(i);
                hashSet.remove(i);
            }
        }

        int[] result = new int[list.size()];

        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }

        return result;
    }
}

结果

解答成功:
执行耗时:2 ms,击败了93.63% 的Java用户
内存消耗:42.4 MB,击败了41.24% 的Java用户

分析

时间复杂度：
O( n + m )

空间复杂度：
O( n )

代码随想录

https://programmercarl.com/0349.%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%BB%84%E7%9A%84%E4%BA%A4%E9%9B%86.html#%E6%80%9D%E8%B7%AF

思路如图所示：

代码实现

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
27
28
29
30
31
32
33
34
35
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();
        //遍历数组1
        for (int i : nums1) {
            set1.add(i);
        }
        //遍历数组2的过程中判断哈希表中是否存在该元素
        for (int i : nums2) {
            if (set1.contains(i)) {
                resSet.add(i);
            }
        }
      
        //方法1：将结果集合转为数组

        return resSet.stream().mapToInt(x -> x).toArray();
        
        //方法2：另外申请一个数组存放setRes中的元素,最后返回数组
        int[] arr = new int[resSet.size()];
        int j = 0;
        for(int i : resSet){
            arr[j++] = i;
        }
        
        return arr;
    }
}

202. 快乐数※

建议：这道题目也是set的应用，其实和上一题差不多，就是 套在快乐数一个壳子

题目链接： https://leetcode.cn/problems/happy-number/
文章讲解： https://programmercarl.com/0202.%E5%BF%AB%E4%B9%90%E6%95%B0.html

https://www.yuanql.top/2023/06/12/02_leetcode/202.%20%E5%BF%AB%E4%B9%90%E6%95%B0/

题目分析

使用一个 HashSet 用于记录已经走过的数值，如果新出现的数值不是1并且在 HashSet 中，则代表数据出现了循环，此时其就不再可能是快乐数了

官方题解中有一个相对巧妙的方法，具体可以查看下方的博客：
https://www.yuanql.top/2023/06/12/02_leetcode/202.%20%E5%BF%AB%E4%B9%90%E6%95%B0/#%E5%AE%98%E6%96%B9%E9%A2%98%E8%A7%A3

方案一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean isHappy(int n) {

        HashSet<Integer> hashSet = new HashSet<>();
        int temp = 0;
        while (true) {
            while (n != 0) {
                temp += (n % 10) * (n % 10);
                n = n / 10;
            }
            if (hashSet.contains(temp)) {
                if (temp == 1) {
                    return true;
                }
                return false;
            } else {
                hashSet.add(temp);
                n = temp;
                temp = 0;
            }
        }
    }
}

结果

解答成功:
执行耗时:1 ms,击败了85.48% 的Java用户
内存消耗:38.7 MB,击败了47.81% 的Java用户

分析

时间复杂度：
O( )

空间复杂度：
O( )

代码随想录

https://programmercarl.com/0202.%E5%BF%AB%E4%B9%90%E6%95%B0.html

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

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

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

还有一个难点就是求和的过程，如果对取数值各个位上的单数操作不熟悉的话，做这道题也会比较艰难。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean isHappy(int n) {
        Set<Integer> record = new 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. 两数之和※

建议：本题虽然是 力扣第一题，但是还是挺难的，也是 代码随想录中 数组，set之后，使用map解决哈希问题的第一题。

建议大家先看视频讲解，然后尝试自己写代码，在看文章讲解，加深印象。

题目链接： https://leetcode.cn/problems/two-sum/
文章讲解： https://programmercarl.com/0001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C.html

https://www.yuanql.top/2023/03/23/02_leetcode/1.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C/

题目分析

遍历数组。先将当前的数值于 HashMap 中的 key 进行比对：
如果不存在，则需要将本数值相关的数据存储到HashMap中，key存储的是 target 减去本数值，此时下一个数值只需要比对此 HashMap 中的 key进行比对就好了。另外 value 数据存储的是当前数值的索引，这样等遇到的时候，就知道其索引了。
如果存在，则意味着此时已经找到的答案，因为 题目中指出只会有一个正确的答案，说明此时找到的就是正确的，取出hashMap中的索引和当前的索引一起形成数组返回即可。

方案一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> hashMap = new HashMap<>(); // key用于存储另外一个数据，value用于存储当前的索引

        for (int i = 0; i < nums.length; i++) {
            if (hashMap.containsKey(nums[i])) {
                return new int[]{hashMap.get(nums[i]), i};
            } else {
                hashMap.put((target - nums[i]), i);
            }
        }
        return new int[]{0, 1};
    }
}

结果

解答成功:
执行耗时:1 ms,击败了98.09% 的Java用户
内存消耗:42.7 MB,击败了19.65% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( n )

代码随想录

https://programmercarl.com/0001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C.html

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

本题呢，我就需要一个集合来存放我们遍历过的元素，然后在遍历数组的时候去询问这个集合，某元素是否遍历过，也就是 是否出现在这个集合。

那么我们就应该想到使用哈希法了。

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

再来看一下使用数组和set来做哈希法的局限。

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

此时就要选择另一种数据结构：map ，map是一种key value的存储结构，可以用key保存数值，用value在保存数值所在的下标。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] twoSum(int[] nums, int target) {
    int[] res = new int[2];
    if(nums == null || nums.length == 0){
        return res;
    }
    Map<Integer, Integer> map = new HashMap<>();
    for(int i = 0; i < nums.length; i++){
        int temp = target - nums[i];   // 遍历当前元素，并在map中寻找是否有匹配的key
        if(map.containsKey(temp)){
            res[1] = i;
            res[0] = map.get(temp);
            break;
        }
        map.put(nums[i], i);    // 如果没找到匹配对，就把访问过的元素和下标加入到map中
    }
    return res;
}
02_1_代码随想录算法训练营18期
#LeetCode #算法训练营
05、第三章 哈希表part01
http://yuanql.top/2023/07/17/02_1_代码随想录算法训练营18期/05、第三章 哈希表part01/
作者
Qingli Yuan
发布于
2023年7月17日
许可协议