Sail


手在键盘敲很轻


Tow-Sum

前言

本文是对daily-algorithms第一题的记录


题目描述

本题难度:★

给定一个整数数组,其中有两项之和为一个特定的数字,假设每次 input 只有一个唯一解,不允许两次使用同一个元素,返回这两个数的索引。

比如:

1
2
3
4
给定 nums = [2, 7, 11, 15],target = 9

由于 nums[0] + nums[1] = 9
所以返回 [0, 1]

答案

解法一

1
2
3
4
5
6
7
8
9
const resolveTwoSum = (nums, target) => {
for (let i = 0; i < nums.length - 1; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i,j];
}
}
}
}

这是很常规的解法,很容易就想出来了

解法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var twoSum = function(nums, target) {
var result = [];
var map = {};
var temp;
for (var i = 0, len = nums.length; i < len; i++) {
temp = target - nums[i];
if (map[temp] !== undefined) {
result[0] = map[temp] ;
result[1] = i;
return result;
}
map[nums[i]] = i;
}
return -1;
};

借用对象字面量,对 ‘“是否存在另一个数” 与 “当前遍历的数” 之和为 target’ 这个问题进行判断。化 O(n^2) 为 O(n)。
其实就是HashMap

1
2
3
4
5
6
var hashMap = {   
Set : function(key,value){this[key] = value},
Get : function(key){return this[key]},
Contains : function(key){return this.Get(key) === null?false:true},
Remove : function(key){delete this[key]}
}

推荐阅读

Hash表
HashMap的JavaScript简洁实现

© 2016-2019. | 由Hexo强力驱动 | 主题Huno | 渝ICP备17002561号 | 不装弱了,我要做大佬