1 两数之和

2026年3月1日

一、题目

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

二、题解

2.1 哈希

思路： 一边遍历数组一边用哈希表记录已经见过的 数值 -> 下标。对每个 nums[i]，先查表中是否存在 target - nums[i]，存在即找到答案；否则把当前数存入表中。这样把暴力的两层循环优化为一次遍历，查找补数为 $O(1)$ 。


class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 创建一个哈希表，用于存储已经遍历过的数字及其对应的索引
        // key: 数组中的某个数值
        // value: 该数值在数组中的下标位置
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();

        // 遍历整个数组，逐个检查每个元素
        for (int i = 0; i < nums.length; i++) {

            // 计算目标值与当前数值的差值
            // 如果哈希表中存在这个差值，说明之前已经遍历过一个数，
            // 这个数 + 当前数 = target，即找到了答案
            if (hashtable.containsKey(target - nums[i])) {

                // 返回两个数的索引：
                // hashtable.get(target - nums[i]) 是之前那个数的索引
                // i 是当前数的索引
                return new int[]{hashtable.get(target - nums[i]), i};
            }

            // 如果没有找到配对，将当前数及其索引存入哈希表
            // 这样后面的数可以与当前数进行配对检查
            hashtable.put(nums[i], i);
        }

        // 如果遍历完数组都没有找到，返回空数组（根据题意，一定有解，这里不会执行）
        return new int[0];
    }
}

时间复杂度： $O(n)$

空间复杂度： $O(n)$

一、题目

二、题解

2.1 哈希

评论