1. Two Sum
1. Two Sum
题目
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)