JavaScript LeetCode

【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.

特色标签
JavaScript LeetCode
链友
ESC