LeetCode 1. 两数之和

Categories:

Tags:

题目描述
思路分析
1. 解法一：哈希表一次遍历（推荐）
2. 解法二：哈希表两次遍历
相似题目

题目描述

✅ 1. 两数之和

题目：

给定一个整数数组 nums 和一个整数目标值 target，在该数组中找出和为目标值的两个整数，并返回它们的下标。每种输入只有唯一一个答案，且同一个元素不能使用两次，可按任意顺序返回答案。

示例 1：

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

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
只存在一个有效答案

进阶：

能否设计时间复杂度低于 O(n^2) 的算法？

思路分析

解法一：哈希表一次遍历（推荐）

核心思路：

边遍历边记录 value -> index。

对于当前元素 nums[i]，检查 target - nums[i] 是否已出现。

若已出现，直接返回两个下标；否则将当前元素加入哈希表。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(n)，其中 n 表示哈希表大小。

// 一次遍历哈希表
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (map.containsKey(need)) {
                return new int[]{map.get(need), i};
            }
            map.put(nums[i], i);
        }

        return new int[]{-1, -1};
    }
}

// 一次遍历哈希表
func twoSum(nums []int, target int) []int {
	index := make(map[int]int)

	for i, v := range nums {
		need := target - v
		if j, ok := index[need]; ok {
			return []int{j, i}
		}
		index[v] = i
	}

	return []int{-1, -1}
}

解法二：哈希表两次遍历

核心思路：

第一次遍历构建 value -> index 映射。

第二次遍历时查找 target - nums[i]，并确保不是同一个下标。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(n)，其中 n 表示哈希表大小。

// 两次遍历哈希表
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }

        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (map.containsKey(need) && map.get(need) != i) {
                return new int[]{i, map.get(need)};
            }
        }

        return new int[]{-1, -1};
    }
}

// 两次遍历哈希表
func twoSum(nums []int, target int) []int {
	index := make(map[int]int)
	for i, v := range nums {
		index[v] = i
	}

	for i, v := range nums {
		need := target - v
		if j, ok := index[need]; ok && j != i {
			return []int{i, j}
		}
	}

	return []int{-1, -1}
}

相似题目

题目	难度	考察点
15. 三数之和	中等	排序 + 双指针
18. 四数之和	中等	排序 + 双指针
167. 两数之和 II - 输入有序数组	中等	双指针
560. 和为 K 的子数组	中等	前缀和
653. 两数之和 IV - 输入二叉搜索树	简单	哈希表、DFS
1679. K 和数对的最大数目	中等	哈希表、排序
1711. 大餐计数	中等	哈希表
2006. 差的绝对值为 K 的数对数目	简单	哈希表
2176. 统计数组中相等且可以被整除的数对	简单	枚举
2239. 找到最接近 0 的数字	简单	线性扫描
2367. 等差三元组的数目	简单	哈希表
2395. 和相等的子数组	简单	哈希表
2441. 与对应负数同时存在的最大正整数	简单	哈希集合
2465. 不同的平均值数目	简单	排序 + 双指针
2824. 统计和小于目标的下标对数目	简单	排序 + 双指针
454. 四数相加 II	中等	哈希表

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/24356627