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 发布文章使用：只允许注册用户才可以访问！