【LeetCode-简单】1.两数之和

By yesmore on 2021-09-05
阅读时间 3 分钟
文章共 641
阅读量

要点:两数之和

描述

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

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1:

1
2
3
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例 2:

1
2
输入:nums = [3,2,4], target = 6
输出:[1,2]

示例 3:

1
2
输入:nums = [3,3], target = 6
输出:[0,1]

提示:

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

**进阶:**你可以想出一个时间复杂度小于 O(n2) 的算法吗?

解题

方法一:暴力解法

1
2
3
4
5
6
7
var twoSum = function(nums, target) {
for(var i=0; i < nums.length; i++) {
for (var j=0; j < i; j++){
if ((nums[j]+nums[i]) == target) return [i, j]
}
}
};
效率
  • 55/55 cases passed (100 ms)
  • Your runtime beats 50.77 % of javascript submissions
  • Your memory usage beats 69.06 % of javascript submissions (38.6 MB)

时间复杂度:$O(N^2)$

空间复杂度:$O(1)$


方法二:Map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* @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)
}
};
解析
关键点
  • 求和转换为求差
  • 借助 Map 结构将数组中每个元素及其索引相互对应
  • 以空间换时间,将查找时间从 O(N) 降低到 O(1)
ES6对象:Map

Map是一组键值对的结构,具有极快的查找速度。

1
2
3
4
5
6
var m = new Map([['Michael', 95], ['Bob', 75], ['Tracy', 85]]);

m.get('Michael'); // 95
m.set('Adam', 67); // 添加新的key-value
m.has('Adam'); // 是否存在key 'Adam': true
m.delete('Adam'); // 删除key 'Adam'
效率
  • 55/55 cases passed (64 ms)
  • Your runtime beats 97.8 % of javascript submissions
  • Your memory usage beats 36.62 % of javascript submissions (39.9 MB)

时间复杂度:$O(N)$

空间复杂度:$O(N)$


方法三:hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
const twoSum = function(nums, target) {
const hash = {}
for(let i = 0; i < nums.length; i++) {
const n = nums[i]
if (hash[target - n] !== undefined)
return [hash[target-n], i]
hash[n] = i
}
return []
};
效率
  • 55/55 cases passed (104 ms)
  • Your runtime beats 47.92 % of javascript submissions
  • Your memory usage beats 67.84 % of javascript submissions (38.6 MB)

时间复杂度:$O(N)$

空间复杂度:$O(N)$


Tips: Please indicate the source and original author when reprinting or quoting this article.