跳至主要內容

1. 两数之和


1. 两数之和

🟢   🔖  数组 哈希表  🔗 力扣open in new window LeetCodeopen in new window

题目

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up totarget.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6

Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6

Output: [0,1]

Constraints:

  • 2 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n^2) time complexity?

题目大意

在数组中找到 2 个数之和等于给定值的数字,结果返回 2 个数字在数组中的下标。

解题思路

使用哈希表,顺序扫描数组,对每一个元素,在 object 中找能组合给定值的另一半数字,如果找到了,直接返回 2 个数字的下标即可。如果找不到,就把这个数字存入 object 中,等待扫到“另一半”数字的时候,再取出来返回结果。

复杂度分析

  • 时间复杂度O(n),其中 n 是字符串的长度。
  • 空间复杂度O(k),其中 kobject 中存放的数字数量,最坏情况下,需要扫描到最后一个数字才能找到结果,此时 k 会趋近 n

代码

var twoSum = function (nums, target) {
	const numsObj = {};
	for (i = 0; i < nums.length; i++) {
		const another = target - nums[i];
		if (another in numsObj) {
			return [numsObj[another], i];
		}
		numsObj[nums[i]] = i;
	}
};

相关题目

题号标题题解标签难度力扣
15三数之和[✓]数组 双指针 排序🟠🀄️open in new window 🔗open in new window
18四数之和[✓]数组 双指针 排序🟠🀄️open in new window 🔗open in new window
167两数之和 II - 输入有序数组[✓]数组 双指针 二分查找🟠🀄️open in new window 🔗open in new window
170两数之和 III - 数据结构设计 🔒设计 数组 哈希表 2+🟢🀄️open in new window 🔗open in new window
560和为 K 的子数组[✓]数组 哈希表 前缀和🟠🀄️open in new window 🔗open in new window
653两数之和 IV - 输入二叉搜索树 深度优先搜索 广度优先搜索 4+🟢🀄️open in new window 🔗open in new window
1099小于 K 的两数之和 🔒数组 双指针 二分查找 1+🟢🀄️open in new window 🔗open in new window
1679K 和数对的最大数目[✓]数组 哈希表 双指针 1+🟠🀄️open in new window 🔗open in new window
1711大餐计数数组 哈希表🟠🀄️open in new window 🔗open in new window
2006差的绝对值为 K 的数对数目数组 哈希表 计数🟢🀄️open in new window 🔗open in new window
2023连接后等于目标字符串的字符串对数组 哈希表 字符串 1+🟠🀄️open in new window 🔗open in new window
2200找出数组中的所有 K 近邻下标数组 双指针🟢🀄️open in new window 🔗open in new window
2351第一个出现两次的字母位运算 哈希表 字符串 1+🟢🀄️open in new window 🔗open in new window
2354优质数对的数目位运算 数组 哈希表 1+🔴🀄️open in new window 🔗open in new window
2367等差三元组的数目数组 哈希表 双指针 1+🟢🀄️open in new window 🔗open in new window
2374边积分最高的节点 哈希表🟠🀄️open in new window 🔗open in new window
2395和相等的子数组数组 哈希表🟢🀄️open in new window 🔗open in new window
2399检查相同字母间的距离数组 哈希表 字符串🟢🀄️open in new window 🔗open in new window
2441与对应负数同时存在的最大正整数数组 哈希表 双指针 1+🟢🀄️open in new window 🔗open in new window
2465不同的平均值数目数组 哈希表 双指针 1+🟢🀄️open in new window 🔗open in new window
2824统计和小于目标的下标对数目数组 双指针 二分查找 1+🟢🀄️open in new window 🔗open in new window