两数之和：哈希表解法

然而 n 个元素两两组合共有 n(n-1)/2 种组合，逐一验证会使时间复杂度达到 O(n²)。

虽然已经完成了题目的要求，但是仍有十分大的优化空间。

解法二（哈希表）

解法一中的大部分时间都用在了验证是否存在 b 元素上，那么我们有没有什么方法来缩短这一流程呢？有的，这个方法就是——'哈希表'。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 使用哈希表可将时间复杂度优化至 O(1)
        // 使用 new 动态分配存储空间，注意 <> 不能忘记
        // 若开头使用 import java.util.HashMap 则此处可直接使用 HashMap
        // 第一个 Integer 为数组元素（key），第二个 Integer 为数组下标（value）
        java.util.HashMap<Integer, Integer> map = new java.util.HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            // map.containsKey() 用于判断键是否存在于哈希表中，返回值为 bool 类型
            if (map.containsKey(complement)) {
                // map.get() 用于查找 Key = complement 对应的 value
                return new int[]{map.get(complement), i};
            }
            // map.put(a,b) 表示存入键值对 a-b，其中 a 为键，b 为值
            map.put(nums[i], i);
        }
        return new int[0];
    }
}

1. 有关哈希表

原理

哈希表（Hash Table）是一种通过键（Key）直接访问值（Value）的数据结构，其核心思想是利用哈希函数将键映射到存储位置（称为哈希桶或槽位）。这种映射使得查找、插入和删除操作的平均时间复杂度接近 O(1)。

当我们在哈希表中存储元素（value）时，我们需要为其绑定一个键（key），系统会使用哈希函数计算该元素的存储位置。例如，对字符串键 "apple" 的简单哈希函数可能是字符 ASCII 码之和取模表大小： hash("apple") = (97 + 112 + 112 + 108 + 101) % table_size 于是系统便会按照计算得到的值为元素分配存储空间，并将 key-value 作为一个整体（entry）存入表中。当我们下次查找该元素时，系统会再次计算该元素的键（key）哈希值，并根据该值去计算元素的存储位置。使用哈希表可将单次查找 / 插入操作的平均时间复杂度优化至 O(1)，整体算法的时间复杂度优化至 O(n)。

2. 关于本题的解题思路

首先先来介绍下代码中使用到的语法及作用。

初始化

// 先 import 后使用
import java.util.HashMap;
HashMap<Integer, Integer> map = new HashMap<>();

// 使用全限定域名
java.util.HashMap<Integer, Integer> map = new java.util.HashMap<>();

(需注意，哈希表中的类型声明首字母应大写，如：Integer、Double、String、Boolean)

判断键是否存在

map.containsKey(key)

存储键值对

map.put(key, value)

根据键获取值

map.get(key)

本题的操作对象为数组，简直完美符合哈希表的应用场景（数组下标和数组元素完美组成键值对）。由于解法二的思路是在哈希表中查找补数 complement 并返回其数组下标，于是我们顺理成章将数组元素作为 key，将数组下标作为 value。

首先对数组进行遍历：

for (int i = 0; i < nums.length; i++)

计算补数 complement：

int complement = target - nums[i]

接下来开始判断 complement 是否存在于哈希表中。若存在则直接返回 complement (即为哈希表中的 key) 在哈希表中的 value（即为 complement 的数组下标）和当前元素的数组下标：

if (map.containsKey(complement)) {
    return new int[]{map.get(complement), i};
}

但哈希表初始为空，那怎么能根据 key 查得到对应的 value 呢？

这个问题很好解决，我们可以在查找 complement 失败后将当前数组元素和数组下标作为键值对存储进哈希表：

map.put(nums[i], i);

因为题目要求是

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

所以 complement 的范围已经确定，当将数组遍历完成后，所有的数组元素（即所有可能存在的 complement）也都存储到了哈希表中。

那对第一个元素的 complement 进行查询的时候，哈希表为空，会不会导致数组元素中原本有他的 complement，但由于后面元素还没有存储进哈希表，导致漏解呢？

我们应该这么想，补数是相互的，比如 2 + 7 = 9，那么 2 的补数就是 7，同样 7 的补数就是 2。假设数组长度为 5，2 为第一个数组元素，7 为第四个数组元素，在哈希表中对 2 进行补数查找时，哈希表为空，查找失败，于是将数组元素 2 及其数组下标作为键值对存储进哈希表，等到数组元素遍历到 7 时，其补数为 2，而 2 已经在哈希表中，补数查找成功。

由此可见并不会出现漏解的情况。