两数组之和

题面分析

题目要求在一个整数数组 nums 中找出两个数，使得它们的和等于给定的目标值 target，并返回这两个数的数组下标。题目保证每种输入只会对应一个答案，并且不能使用两次相同的元素。

解题思路

1. 暴力枚举法：最直观的方法是使用双重循环，遍历数组中的每一对数，检查它们的和是否等于 target。这种方法的时间复杂度为 $O(n^2)$，在数据量较大时效率较低。

2. 哈希表法：为了提高效率，可以使用哈希表（字典）来存储数组中的元素及其对应的下标。遍历数组时，对于每个元素 nums[i]，检查 target - nums[i] 是否在哈希表中。如果存在，则返回这两个数的下标；否则，将当前元素及其下标存入哈希表。这种方法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

LeetCode 1. 两数之和-原题链接

题目内容

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

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

你可以按任意顺序输出答案。

输入描述

输入共两行。

• 第一行为两个个整数$n，target$，代表数组$nums$的长度和目标值。

• 第二行为$n$个整数$nums_0,nums_1,...,nums_{n-1}$，数字之间以空格分隔。

输出描述

一行两个整数，以空格分隔，表示两个元素的数组下标。

样例1

输入

4 9
2 7 11 15

输出

0 1

说明

因为 $nums[0] + nums[1] == 9$ ，输出$0, 1$

样例2

输入

3 6
3 2 4

输出

1 2

提示

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