iT邦幫忙

1

使用javascript來解leetcode(#1 Two Sum)(Easy)

Leo 2020-06-24 10:15:12396 瀏覽

#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和5,數字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)];
    }
}
//將班上同學的成績與櫃子號碼用Map紀錄
//直覺會想說要將櫃子號碼存在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數字重複使用

參考文章

如果文章內容有任何問題或意見麻煩留言給我知道
感謝您


尚未有邦友留言

立即登入留言