# 「力扣」第 1 题：两数之和（简单）
# 视频讲解
这道题在 官方题解 (opens new window) 和 B 站 (opens new window) 可以收看视频讲解，选择快速播放，获得更好的观看体验。
# 题目描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
- 只会存在一个有效答案
进阶： 你可以想出一个时间复杂度小于
# 方法一：暴力解法
参考代码 1：
public class Solution {
public int[] twoSum(int[] nums, int target) {
int len = nums.length;
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
throw new RuntimeException("没有找到和为 target 的两个数。");
}
}
复杂度分析：
- 时间复杂度：
，其中 是输入数组的长度； - 空间复杂度：
。
# 方法二：哈希表
在遍历的过程中记住已经遍历过的元素的值和下标，因此使用「哈希表」记录看到的元素的「值」和「下标」的对应关系。
参考代码 2：
Java 代码：
import java.util.HashMap;
import java.util.Map;
public class Solution {
public int[] twoSum(int[] nums, int target) {
int len = nums.length;
Map<Integer, Integer> hashMap = new HashMap<>(len - 1);
hashMap.put(nums[0], 0);
for (int i = 1; i < len; i++) {
int another = target - nums[i];
if (hashMap.containsKey(another)) {
return new int[]{i, hashMap.get(another)};
}
hashMap.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
}
Python3 代码：
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
map = dict()
for index, num in enumerate(nums):
if target - num in map:
return [index, map[target - num]]
else:
map[num] = index
复杂度分析：
- 时间复杂度：
，其中 是输入数组的长度； - 空间复杂度：
。
思路：用集合 Set 做差补来完成（推荐）
Python 代码：
class Solution(object):
def findNumbersWithSum(self, nums, target):
s = set()
for num in nums:
if target - num not in s:
s.add(num)
else:
return [num, target - num]
作者：liweiwei1419 链接：https://suanfa8.com/hash-table/solutions/0001-two-sum 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。