1. 两数之和

🟢   🔖  数组 哈希表  🔗 力扣 LeetCode

题目

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(n2) time complexity?

题目大意

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

解题思路

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

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度。
• 空间复杂度：O(k)，其中 k 是 object 中存放的数字数量，最坏情况下，需要扫描到最后一个数字才能找到结果，此时 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	三数之和	[✓]	数组 双指针 排序
18	四数之和	[✓]	数组 双指针 排序
167	两数之和 II - 输入有序数组	[✓]	数组 双指针 二分查找
170	两数之和 III - 数据结构设计 🔒		设计 数组 哈希表 2+
560	和为 K 的子数组	[✓]	数组 哈希表 前缀和
653	两数之和 IV - 输入二叉搜索树		树 深度优先搜索 广度优先搜索 4+
1099	小于 K 的两数之和 🔒		数组 双指针 二分查找 1+
1679	K 和数对的最大数目	[✓]	数组 哈希表 双指针 1+
1711	大餐计数		数组 哈希表
2006	差的绝对值为 K 的数对数目		数组 哈希表 计数
2023	连接后等于目标字符串的字符串对		数组 哈希表 字符串 1+
2200	找出数组中的所有 K 近邻下标		数组 双指针
2351	第一个出现两次的字母		位运算 哈希表 字符串 1+
2354	优质数对的数目		位运算 数组 哈希表 1+
2367	等差三元组的数目		数组 哈希表 双指针 1+
2374	边积分最高的节点		图 哈希表
2395	和相等的子数组		数组 哈希表
2399	检查相同字母间的距离		数组 哈希表 字符串
2441	与对应负数同时存在的最大正整数		数组 哈希表 双指针 1+
2465	不同的平均值数目		数组 哈希表 双指针 1+
2824	统计和小于目标的下标对数目		数组 双指针 二分查找 1+