LeetCode 算法题解 js 版 (001 Two Sum)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

LeetCode 算法题解 js 版 (001 Two Sum)

两数之和

https://leetcode.com/problems/two-sum/submissions/

https://leetcode-cn.com/problems/two-sum/submissions/

1. 暴力解法

Time complexity: O(n**2)

Space complexity: O(n)


"use strict";/**
* @author xgqfrms
* @description leetcode problems: two-sum & https://leetcode.com/problems/two-sum/
* @language JavaScript & ES6
*
* @param {Int Number Array} nums
* @param {Int Number} target
* @return {Int Number Array} result
*
*/let twoSum = (nums = [2, 7, 11, 15], target = 9) => {
let result = [];
for(let i = 0; i < nums.length; i++){
for(let ii = 0; ii < nums.length; ii++){
let temp_a = nums[i];
let temp_b = nums[ii];
if(ii !== i){
let temp_result = temp_a + temp_b;
if(temp_result === target){
// 1. reset;
// result = [];
// result.push(i);
// result.push(ii);
// 2. remove duplication
if(!result.includes(i)){
result.push(i);
}
if(!result.includes(ii)){
result.push(ii);
}
result.sort();
}
}else{
// break;
}
}
}
return result;
};

2. 一遍 Hash Table

Time complexity: O(n)

Space complexity: O(n)


// Time complexity: O(n)
// Space complexity: O(n)/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let result = [];
// 空间换时间 HashMap / Object
const obj = {};
for(let i = 0; i < nums.length; i++) {
let temp = target - nums[i];
if(obj[nums[i]] !== undefined) {
result = [obj[nums[i]], i];
break;
} else {
obj[temp] = i;
}
}
return result;
};

ES6

Map & WeakMap

bugs

// bug/*var twoSum = function(nums, target) {
let result = [];
for(let i = 0; i < target; i++) {
let temp = target - i;
if(nums.includes(temp) && nums.includes(i)) {
result = [nums.indexOf(i), nums.indexOf(temp)];
break;
}
}
return result;
};*/

best solutions

https://leetcode-cn.com/submissions/detail/112453419/

/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
var map=new Map();
for(let i=0;i<nums.length;i++){
if(!map.has(target-nums[i])){
map.set(nums[i],i);
}else{
return [map.get(target-nums[i]),i]
}
}
};
/**
* 注：此题使用ES6的Map，使得时间复杂度降为O(n)
* 关于Map和Set的使用要重点掌握！！！
* 我觉得思路很棒，继续理解！
*/

/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let i = nums.length;
while(i > 1) {
let last = nums.pop();
if (nums.indexOf(target - last) > -1){
return [nums.indexOf(target - last),nums.length];
}
i--
}
}

refs

xgqfrms 2012-2020

www.cnblogs.com 发布文章使用：只允许注册用户才可以访问！