Hash Table

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

eg：array、set、map

一般只关注是否出现过用set，而同时要关心出现次数时用map

哈希函数

通过hashCode把元素转化为数值，然后映射到哈希表中

哈希碰撞

两个不同的元素映射到了同一个位置（因为哈希表也是有长度的，所以有可能出现）

解决哈希碰撞的两种方法：拉链法|线性探测法

拉链法

在哈希表的每个元素上指向一个链表，用链表存储发生碰撞的元素

线性探测法

简而言之，当这个位置已经有元素了，那我放下一个位置不就好了，下一个同理。所以就要求数据量要小于哈希表的大小

应用场景

当我们遇到要快速判断一个元素是否出现在集合中|一个元素是否出现过时，就可以考虑哈希法。

242.有效的字母异位词

[242.有效的字母异位词](242. 有效的字母异位词 - 力扣（LeetCode）)

image-20240819215511612

看到这个🧐 如果你想到两层for循环，那么【退！退！退!】 hhh

首先想到可以用map，key是字母，value是出现次数，两个字符串正好一个‘＋’一个‘－’，最后判断map是否有不为0的就可以了

Tips：既然只包含小写字母，那么不用map了呀！也就是不用key了，可以用数组下标代替key！数组的大小可以定义为26

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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是字母异位词
    }
}

454.四数相加II

[454.四数相加II](454. 4Sum II - 力扣（LeetCode）)

image-20240820195112092

要求符合条件的元组个数，而且是4数求和，不能用map保存前3个和找第4个数？

这样要三个for循环呀，不划算不划算

所以应该分两组！用两个for循环

第一批利用map，key保存两数之和，value保存两数之和出现的次数

第二批呢就在两层for循环中判断是否在第一批中找到互补的，找到就把value+到结果中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        //统计两个数组中的元素之和，同时统计出现的次数，放入map
        for (int i : nums1) {
            for (int j : nums2) {
                int sum = i + j;
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }
        //统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
        for (int i : nums3) {
            for (int j : nums4) {
                res += map.getOrDefault(0 - i - j, 0);
            }
        }
        return res;
    }
}

15. 三数之和

[15. 三数之和](. - 力扣（LeetCode）)

image-20240821164044612

用哈希表保存前两个数的和，寻找0−a−b0-a-b是不是在数组中这是一般思路，但是这里有一个问题：不重复！

哈希表保存两个数的和再去重比较复杂，看一下有没有别的思路？

排序+双指针

  1. 通过排序使数组从小到大
  2. 开始遍历ii
    • 当下标ii的元素大于0时，直接break
    • 当下标ii的元素和下标i−1i-1的元素相同，直接continue
    • 当不满足前两个条件时，就要开始判断了：定义两个指针分别指向i+1和nums.length-1，如果三数之和大于0则right左移，反之右移，直到left<=right。如果找到满足条件的组合，那么left++，right--，此时要进行去重
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
36
37
38
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
	// 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        for (int i = 0; i < nums.length; i++) {
	    // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
            if (nums[i] > 0) { 
                return result;
            }

            if (i > 0 && nums[i] == nums[i - 1]) {  // 去重a
                continue;
            }

            int left = i + 1;
            int right = nums.length - 1;
            while (right > left) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
		    // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;
                    
                    right--; 
                    left++;
                }
            }
        }
        return result;
    }
}