51 lines
1.6 KiB
Markdown
51 lines
1.6 KiB
Markdown
|
## 题目地址
|
|||
|
|
https://leetcode-cn.com/problems/two-sum
|
|||
|
|
|
|||
|
|
## 题目描述
|
|||
|
|
```
|
|||
|
|
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
|
|||
|
|
|
|||
|
|
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
|
|||
|
|
|
|||
|
|
示例:
|
|||
|
|
|
|||
|
|
给定 nums = [2, 7, 11, 15], target = 9
|
|||
|
|
|
|||
|
|
因为 nums[0] + nums[1] = 2 + 7 = 9
|
|||
|
|
所以返回 [0, 1]
|
|||
|
|
```
|
|||
|
|
## 思路
|
|||
|
|
最容易想到的就是暴力枚举，我们可以利用两层 for 循环来遍历每个元素，并查找满足条件的目标元素。不过这样时间复杂度为 O(N^2)，空间复杂度为 O(1)，时间复杂度较高，我们要想办法进行优化。我们可以增加一个 Map 记录已经遍历过的数字及其对应的索引值。这样当遍历一个新数字的时候去 Map 里查询，target 与该数的差值是否已经在前面的数字中出现过。如果出现过，那么已经得出答案，就不必再往下执行了。
|
|||
|
|
|
|||
|
|
## 关键点
|
|||
|
|
|
|||
|
|
- 求和转换为求差
|
|||
|
|
- 借助 Map 结构将数组中每个元素及其索引相互对应
|
|||
|
|
- 以空间换时间，将查找时间从 O(N) 降低到 O(1)
|
|||
|
|
|
|||
|
|
## 代码
|
|||
|
|
* 语言支持：JS
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
/**
|
|||
|
|
* @param {number[]} nums
|
|||
|
|
* @param {number} target
|
|||
|
|
* @return {number[]}
|
|||
|
|
*/
|
|||
|
|
const twoSum = function (nums, target) {
|
|||
|
|
const map = new Map();
|
|||
|
|
for (let i = 0; i < nums.length; i++) {
|
|||
|
|
const diff = target - nums[i];
|
|||
|
|
if (map.has(diff)) {
|
|||
|
|
return [map.get(diff), i];
|
|||
|
|
}
|
|||
|
|
map.set(nums[i], i);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
***复杂度分析***
|
|||
|
|
|
|||
|
|
- 时间复杂度：O(N)
|
|||
|
|
- 空间复杂度：O(N)
|