#1 Two Sum

medium版本

题目原文

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0, 1].

题目网址

题目翻译

给予一组数列nums给予一个target目标值从数列nums中找出两个数字相加是target值将两个数字在数列中的位置回传input数列只会找到一组可以合成target值的解(像是如果target=8则输入数列不可能是[3,5,6,2]，因为有两组解数字3和５，数字6和2)每个数字不能重複使用(比如target=4，输入数列[2,1,5]，不能将数字2使用二次来合成4)

解题思路

假设情境

某次资料结构的期中考，老师因为太多同学常常翘课所以起赌烂，决定出一份超难的考卷，下定决心要当掉一半的人。聪明的小明，在那次考试中拿到60分(target)的成绩，逃过被老师当掉的风险，但天生个性白烂的他，决定去取笑那些考得比他低的同学，要找两个加起来才刚好和他分数一样60分的同学取笑。小明知道同学都把考卷放在自己的置物柜里，因此决定要翻同学的柜子，偷拿出他们的考卷来当面取笑。

暴力破解法(Brute Force)

小明来到同学的柜子，先开了第一个柜子发现是自己平常很讨厌的小华，只考了34分。小明很想取笑他，因此开始从第一个柜子之后依序翻柜子，要找出只有考26分的同学，用来取笑小华，但是后来将全部柜子都看过一遍，却发现全班没有人考26分??，只好又以2号柜子考33分的小美当基準，要找考27分的同学。由于他先前没有纪录每个柜子的同学考几分，因此又要重头开始翻同学的柜子，最后终于在第45号柜子找到考27分的同学，偷出他们的考卷，却也浪费一堆时间。

let twoSum = function(nums, target) {for(let x=0;x<nums.length;x++){let goal=target-nums[x];for(let y=x+1;y<=nums.length;y++){if(nums[y]===goal)    return [x,y];        }    }}//nums[]表示柜子里的考卷分数//target表示小明的成绩//nums[x]小华的成绩//goal代表小明成绩与小华成绩相减的值，另一位他要嘲笑的同学//x,y代表柜子号码

使用dictionaries概念

Map、 dictionaries、associative arrays、hashtable 都是一样的概念，一种用key:value来表达关係的资料结构，就把他想像成key是书页而value是内容，透过索引key来快速找到所要的值value，而不同程式语言有不同的实作方式。

又经过了一次期末考，白烂的小明又再次出动了，这次他考了70分，也一样决定找两位同学嘲笑。但是这次他学聪明了，先依序打开同学柜子后，将同学的分数与柜子号码用表格纪录下来。然后从第一个柜子小华考了34分为基準，快速透过表格找到考26分的阿呆是在20号柜子，快速将两人考卷拿走。

//使用Map实作let twoSum = function(nums, target) {let Mymap = new Map();for(let i=0;i<nums.length;i++){    Mymap.set(nums[i],i);}for(let x=0;x<nums.length;x++){let goal=target-nums[x];    if(Mymap.has(goal)&&x!=Mymap.get(goal))        return[x,Mymap.get(goal)];    }}//将班上同学的成绩与柜子号码用Ｍap纪录//直觉会想说要将柜子号码存在key，成绩存value//但是最后题目是要回传柜子号码，因此将柜子号码放在value，之后方便get得到值//set(key,value)将资料加入表格//get(key)用key得到value//x!=Mymap.get(goal)预防x数字重複使用

//使用Object实作let twoSum = function(nums, target) {let dict={};for(let i=0;i<nums.length;i++){    dict[nums[i]]=i;}for(let x=0;x<nums.length;x++){let goal=target-nums[x];    if(goal in dict&&x!=dict[goal])            return[x,dict[goal]];}}//将班上同学的成绩与柜子号码用object纪录//直觉会想说要将柜子号码存在key，成绩存value//但是最后题目是要回传柜子号码，因此将柜子号码放在value，之后方便得到值//设定值dict[key]=value//in用法是会看goal值有没有出现在object的key过，有就回传true//x!=dict[goal]预防x数字重複使用

参考文章

Map使用方式Object in使用方式

如果文章内容有任何问题或意见麻烦留言给我知道
感谢您