哈希表

发表于 更新于 分类于 ， 本文字数： 1.4k 阅读时长 ≈ 5 分钟 阅读次数：

相似解法题目多元组

  • 哈希表：<BM50 两数之和，BM54 三数之和>

BM50 两数之和

描述

给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。

注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到。

思路

哈希表

如果数组中出现的一个数 a，目标值减去 a 的值已经出现过了，那么这就是我们要找的一对元组。

快速找到已经出现过的某个值，可以使用哈希表快速检验某个元素是否出现过的功能。

F1：哈希表

步骤
  1. 构建一个哈希表，key 为遍历数组过程中出现过的值，value 为其相应的下标，因为最终要返回的是下标。
  2. 遍历数组每个元素，如果目标值减去该元素的结果在哈希表中存在，说明我们先前遍历的时候它出现过，根据记录的下标，就可以得到结果。
  3. 如果相减后的结果没有在哈希表中，说明先前遍历的元素中没有它对应的另一个值，那我们将当前数组元素加入哈希表中，等待后续它匹配的那个值出现即可。
  4. 需要注意最后的结果是下标值加 1。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] twoSum (int[] numbers, int target) {
    int[] res = new int[0];
    // 1. 创建哈希表,两元组分别表示值、下标
    HashMap<Integer, Integer> map = new HashMap<>();
    // 2. 遍历数组，在哈希表中查找 target - numbers[i]
    for (int i = 0; i < numbers.length; i++) {
        int tmp = target - numbers[i];
        // 3. 若是没找到，将当前数组元素和下标计入哈希表
        if (!map.containsKey(tmp)) {
            map.put(numbers[i], i);
        } else {
            // 4. 否则返回两个下标 +1
            return new int[] {map.get(tmp) + 1, i + 1};
        }
    }
    return res;
}
时间复杂度

\(O(n)\)

仅仅遍历数组一次，每次查询哈希表都是 \(O(1)\)

空间复杂度

\(O(n)\)

最坏情况下，遍历到数组结尾才找到，其他都加入哈希表，因此哈希表最长为 n - 1 的长度。

BM54 三数之和

描述

给出一个有 n 个元素的数组 S，S 中是否有元素 a, b, c 满足a+b+c=0？找出数组 S 中所有满足条件的三元组。

注意：

  1. 三元组（a、b、c）中的元素必须按非降序排列。（即 a≤b≤c）
  2. 解集中不能包含重复的三元组。

例如，给定的数组 S = {-10 0 10 20 -10 -40}，解集为 [(-10, -10, 20), (-10, 0, 10)]

思路

哈希表、双指针

直接找三个数字之和为某个数，太过麻烦。可以进行拆分：如果找到了某个数 a，要找到与之对应的另外两个数，三数之和为 0，那只要找到另外两个数之和为 -a 即可。

因为三元组内部必须有序，可以优先对原数组排序，每次取一个最小的数为 a，只需要在后续数组中找到两个和为 -a 就可以了。可以使用双指针缩小区间，因为太后面的数字太大了，就不可能为 -a，可以舍弃。

F1：哈希表+双指针

步骤
  1. 排除边界特殊情况；
  2. 要求三元组内部必须有序，因此对原数组使用 sort 函数排序；
  3. 得到有序数组后，遍历该数组，对于每个遍历到元素，假设它是三元组中最小的一个，那么另外两个一定在后面。
  4. 需要三个数相加为 0，则另外两个数相加应该为上述第一个数的相反数，我们可以利用双指针在剩余的子数组中找有没有这样的数对。双指针指向剩余子数组的首尾，如果二者相加为目标值，那么就可以记录，而且二者中间数字相加可能还会有。
  5. 如果二者相加大于目标值，说明右指针太大了，那么就将其左移缩小，相反如果二者相加小于目标值，说明左指针太小了，将其右移扩大，直到两指针相遇，剩余子数组找完了。

注意：对于三个数字都要判断是否相邻有重复的情况，要去重。

代码
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
39
40
41
42
43
44
45
46
public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        int n = num.length;
        // 1. 边界：不够三元组
        if (n < 3) {
            return ans;
        }
        // 2. 对原数组排序
        Arrays.sort(num);
        // 3. 遍历数组
        for (int i = 0; i < n - 2; i++) {
            // 去重
            if (i != 0 && num[i] == num[i - 1])
                continue;
            // 剩余子数组首尾双指针
            int left = i + 1;
            int right = n - 1;
            // 当前目标值：当前值的相反数（-a）
            int target = -num[i];
            while (left < right) {
                // 4. 双指针指向的两值相加为 target，则可以与 num[i] 组成 0
                if (num[left] + num[right] == target) {
                    ArrayList<Integer> tmp = new ArrayList<>();
                    tmp.add(num[i]);
                    tmp.add(num[left]);
                    tmp.add(num[right]);
                    ans.add(tmp);
                    while (left + 1 < right && num[left] == num[left + 1])
                        left++;// 去重
                    while (right - 1 > left && num[right] == num[right - 1])
                        right--; // 去重
                    // 双指针向中间收缩
                    left++;
                    right--;
                }
                // 5.1 双指针的值之和大于目标值，右指针值太大了，向左移动
                else if (num[left] + num[right] > target) {
                    right--;
                }
                // 5.2 双指针的值之和小于目标值，左指针值太小了，向右移动
                else
                    left++;
            }
        }
        return ans;
    }
时间复杂度

\(O(n^2)\)

排序的复杂度为 \(O(nlog_2n)\)，查找三元组的复杂度为 \(O(n^2)\)

空间复杂度

\(O(1)\)

ans 属于必要空间，不属于额外空间，无其他辅助空间。