LeetCode偶尔一题 —— 1. 两数之和

题目描述📄

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

题目剖析🧐

一、 暴力搜索

  • 双层循环,尝试每一个可能的和
  • 找到 nums[i] + nums[j] === target时返回 [i, j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
const len = nums.length
for (let i = 0; i < len - 1; i++) {
for (let j = i + 1; j < len; j++) {
if (nums[i] + nums[j] === target) {
return [i, j]
}
}
}
}
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)

思路二、空间换时间 —— 巧用哈希表

  • target - nums[i]i 的值存放在 哈希表 中,target - nums[i] 对应 i
  • 遍历一次 nums 数组,找到一个存在于 哈希表 中的 nums[i],即找到两个数字之和等于 target
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
const map = new Map()
for (let i = 0; i < nums.length; i++) {
map.set(target - nums[i], i)
}
for (let i = 0; i < nums.length; i++) {
const ans = map.get(nums[i])
if (ans && ans !== i) {
return [ i, map.get(nums[i]) ]
}
}
}

其实这里还能把循环优化成为一个,代码如下🌰:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
const map = new Map()
for (let i = 0; i < nums.length; i++) {
const ans = target - nums[i]
if (map.has(ans)) {
return [ i, map.get(ans) ]
}
map.set(nums[i], i)
}
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)