1. Two Sum

🟢   🔖  数组 哈希表  🔗 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 个数字在数组中的下标。

解题思路

这道题最优的做法时间复杂度是 O(n)。

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

代码

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 - 输入有序数组
• 🔒 Two Sum III - Data structure design
• 560. 和为 K 的子数组
• 653. 两数之和 IV - 输入二叉搜索树
• 🔒 Two Sum Less Than K
• 1679. K 和数对的最大数目
• 1711. 大餐计数
• 2006. 差的绝对值为 K 的数对数目
• 2023. 连接后等于目标字符串的字符串对
• 2200. 找出数组中的所有 K 近邻下标
• 2351. 第一个出现两次的字母
• 2354. 优质数对的数目
• 2367. 算术三元组的数目
• 2374. 边积分最高的节点
• 2399. 检查相同字母间的距离
• 2395. 和相等的子数组
• 2441. 与对应负数同时存在的最大正整数
• 2465. 不同的平均值数目
• 2824. Count Pairs Whose Sum is Less than Target

- [15. 三数之和](./0015.md)
- [18. 四数之和](./0018.md)
- [167. 两数之和 II - 输入有序数组](./0167.md)
- [🔒 Two Sum III - Data structure design](https://leetcode.com/problems/two-sum-iii-data-structure-design)
- [560. 和为 K 的子数组](https://leetcode.com/problems/subarray-sum-equals-k)
- [653. 两数之和 IV - 输入二叉搜索树](https://leetcode.com/problems/two-sum-iv-input-is-a-bst)
- [🔒 Two Sum Less Than K](https://leetcode.com/problems/two-sum-less-than-k)
- [1679. K 和数对的最大数目](https://leetcode.com/problems/max-number-of-k-sum-pairs)
- [1711. 大餐计数](https://leetcode.com/problems/count-good-meals)
- [2006. 差的绝对值为 K 的数对数目](https://leetcode.com/problems/count-number-of-pairs-with-absolute-difference-k)
- [2023. 连接后等于目标字符串的字符串对](https://leetcode.com/problems/number-of-pairs-of-strings-with-concatenation-equal-to-target)
- [2200. 找出数组中的所有 K 近邻下标](https://leetcode.com/problems/find-all-k-distant-indices-in-an-array)
- [2351. 第一个出现两次的字母](https://leetcode.com/problems/first-letter-to-appear-twice)
- [2354. 优质数对的数目](https://leetcode.com/problems/number-of-excellent-pairs)
- [2367. 算术三元组的数目](https://leetcode.com/problems/number-of-arithmetic-triplets)
- [2374. 边积分最高的节点](https://leetcode.com/problems/node-with-highest-edge-score)
- [2399. 检查相同字母间的距离](https://leetcode.com/problems/check-distances-between-same-letters)
- [2395. 和相等的子数组](https://leetcode.com/problems/find-subarrays-with-equal-sum)
- [2441. 与对应负数同时存在的最大正整数](https://leetcode.com/problems/largest-positive-integer-that-exists-with-its-negative)
- [2465. 不同的平均值数目](https://leetcode.com/problems/number-of-distinct-averages)
- [2824. Count Pairs Whose Sum is Less than Target](https://leetcode.com/problems/count-pairs-whose-sum-is-less-than-target)