在之前刷力扣的过程中，我每刷道题都是先看题解然后再去边写边看，很多内容根本没消化，在进度上欺骗自己，感觉之前刷的都忘了，能力没有什么提升，现在还是一道都不会做。所以这次报了卡哥的算法训练营，希望能够按计划地有效刷题。本次刷题，我用的是 Java 语言解题，有余力的话也可能会加上 C++ 的题解。以下是算法训练营第六天的刷题记录和思考笔记。

一、哈希表理论基础

哈希表

哈希表（Hash table）是根据关键码的值而直接进行访问的数据结构。

哈希表一般都是用来快速判断一个元素是否出现集合里。例如要查询一个名字是否在这所学校里，要枚举的话时间复杂度是 O(n)，但如果使用哈希表的话， 只需要 O(1) 就可以做到，我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。

哈希函数

将学生姓名映射到哈希表上就涉及到了哈希函数（Hash function）。哈希函数通过 hashCode 把名字转化为数值，一般 hashCode 是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。

如果 hashCode 得到的数值大于哈希表的大小了，也就是大于 tableSize 了，此时为了保证映射出来的索引数值都落在哈希表上，我们会在再次对数值做一个取模的操作，就要我们就保证了学生姓名一定可以映射到哈希表上了。

哈希碰撞

如果学生的数量大于哈希表的大小，此时就算哈希函数计算的再均匀，也避免不了会有几位学生的名字同时映射到哈希表同一个索引下标的位置，这一现象叫做哈希碰撞。

一般哈希碰撞有两种解决方法， 拉链法和线性探测法。

拉链法：刚刚小李和小王在索引 1 的位置发生了冲突，发生冲突的元素都被存储在链表中。 这样我们就可以通过索引找到小李和小王了。

其实拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

使用线性探测法，一定要保证哈希表的大小 tableSize 大于数据规模 dataSize，依靠哈希表中的空位来解决碰撞问题。例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求 tableSize 一定要大于 dataSize ，要不然哈希表上就没有空置的位置来存放冲突的数据了。

常见的三种哈希结构

当我们想使用哈希法来解决问题的时候，我们一般会选择三种数据结构：数组（List）、集合（set）、映射（map）。

• List 是有序可重复集合。

• Set 是无序不可重复集合。

• Map 是以键值对存储的集合，key 不能重复，key 底层也是以 set 存储的。

总结

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

但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set 或者是 map 来存放数据，才能实现快速的查找。

二、242 有效的字母异位词

题目

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

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

1
2

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

解题思路

暴力解法：转换成字符数组，分别排序再比较。时间复杂度：O(nlogn)，空间复杂度：O(logn)。

1
2
3
4
5
6
7
8
9

class Solution {
    public boolean isAnagram(String s, String t) {
        char[] ss = s.toCharArray();
        char[] tt = t.toCharArray();
        Arrays.sort(ss);
        Arrays.sort(tt);
        return Arrays.equals(ss, tt);
    }
}

数组其实就是一个简单哈希表，而且这道题目中字符串只有小写字符，那么就可以定义一个数组，来记录字符串 s 里字符出现的次数。

定义一个数组叫做 record 用来上记录字符串 s 里字符出现的次数，大小为 26 就可以了，初始化为 0，因为字符 a 到字符 z 的 ASCII 也是 26 个连续的数值，字符 a 映射为下标 0，相应的字符 z 映射为下标 25。

再遍历字符串 s 的时候，只需要将 s[i] - ‘a’ 所在的元素做 +1 操作即可，并不需要记住字符 a 的 ASCII，只要求出一个相对数值就可以了。这样就将字符串 s 中字符出现的次数，统计出来了。同样在遍历字符串 t 的时候，对t中出现的字符映射哈希表索引上的数值再做 -1 的操作。

record 数组如果有的元素不为零 0，说明字符串 s 和 t 一定是谁多了字符或者谁少了字符，如果 record 数组所有元素都为零 0，说明字符串 s 和 t 是字母异位词。

时间复杂度为 O(n)，空间上因为定义是的一个常量大小的辅助数组，所以空间复杂度为 O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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']++;
        }
        for (int i = 0; i < t.length(); i++) {
            record[t.charAt(i) - 'a']--;
        }
        for (int count : record) {
            if (count != 0) {
                return false;
            }
        }
        return true;
    }
}

三、349 两个数组的交集

题目

给定两个数组 nums1 和 nums2 ，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。

1
2

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

解题思路

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 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<>();

        for (int i : nums1) {
            set1.add(i);            //遍历数组1
        }

        for (int i : nums2) {
            if (set1.contains(i)) {
                resSet.add(i);      //遍历数组2的过程中判断哈希表中是否存在该元素
            }
        }
        
        return resSet.stream().mapToInt(x -> x).toArray();    //将结果几何转为数组
    }
}

四、202 快乐数

题目

编写一个算法来判断一个数 n 是不是快乐数。如果 n 是快乐数就返回 true ；不是则返回 false 。

快乐数定义为：

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

1
2
3
4
5
6
7

输入：n = 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 是否重复出现，如果重复了就是 return false， 否则一直找到 sum == 1 为止。

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;   // ==1为true，!=1为false
    }

    private int getNextNumber(int n) {    // 取各位置上的数字的平方和
        int res = 0;
        while (n > 0) {
            int temp = n % 10;
            res += temp * temp;
            n = n / 10;
        }
        return res;
    }
}

五、1 两数之和

题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

1
2
3

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

解题思路

梦开始的地方，暴力解法，两个 for 循环：

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

本题需要一个集合来存放我们遍历过的元素，然后在遍历数组的时候去询问这个集合，某元素是否遍历过，也就是是否出现在这个集合。那么我们就应该想到使用哈希法了。

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

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

本题，我们不仅要知道元素有没有遍历过，还要判断这个元素是否出现过，如果出现过，返回这个元素的下标，需要使用 key value 结构来存放，key 来存元素，value 来存下标，使用 map 正合适。

• map 中的存储结构为 {key：数据元素，value：数组元素对应的下标}。
• 在遍历数组的时候，只需要向 map 去查询是否有和目前遍历元素比配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进 map 中，因为 map 存放的就是我们访问过的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public int[] twoSum(int[] nums, int target) {
    int[] res = new int[2];
    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;
}

LeetCode

Bezhuang