iT邦幫忙

DAY 7
2

連續30天,挑戰演算法系列 第 7

[Day07] 30天挑戰演算法 - 配對之合

題目來源Two Sum

問題
給一個陣列和一個 目標數字,試著從這陣列中找出兩個數字,並且這兩個數字的 會等於 目標數字
此外陣列的 index 從 1 開始(不是從0), 並且為了確保不會有兩種答案,所以題目還有特別要求在回傳的兩個 index 中, index1 要小於 index2

例子
假設陣列為: [2, 7, 11, 15], 目標數字為 9
則答案為 index1=1, index2=2

想法
I. 暴力法:
用兩個回圈去完成,其時間複雜度為 O(N^2)
其做法就是
for i from 1 to N {
for j from i+1 to N {
if ( array + array[j] is equal target number )
return {i, j}
}
}

不過如果使用暴力法上去 LeetCode OJ 上去測試的話,你會得到這樣一個訊息:
Time Limit Exceeded 也就是說,你花的時間太久了,雖然答案可能是正確的。但效率太差!
所以我們得另外找一個方法才行!

記得多年以前看過一部電視劇「保鏢」,其中有一幕是這樣說的:
『給你三個盤子,第一個盤子放滿了紅豆綠豆。你要在一個時辰之內用筷子把 紅豆 跟 綠豆 分開到兩個盤子中。這時候女主角怎麼樣也無法在一個時辰之用筷子內分別把紅豆、綠豆分開來。直到最後他開悟了才完成!』

原來他是在一個時辰之內把第一個盤子裡的紅豆全部夾到第二個盤子。這樣就完成了!
所以我們這一題也是可以用相同的方法,不要執著於要找到兩個數相加等於 目標數字,我們也可以用 目標數字 減掉 陣列裡的數字而找到另一個數字,這樣一來效率就會提高很多!

虛擬碼
HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
for i from 1 to the end
要找的數字 = targetNumber - 陣列[i];
若 hashMap 包含 key 為 要找的數字
則 index1 就會等於 hashMap.get(要找的數字), index2 就會等於 i
否則
將 i 跟 陣列[i] 存入 hashMap, 用 陣列[i] 當 key, i 當 value

解答 - Java 版本
public int[] findTwoSumIndex(int[] numbers, int target) {
HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();

for(int i=0; i< numbers.length; i++) {
int findNumber = target - numbers[i];

if (hashMap.containsKey(findNumber)){
int x = hashMap.get(findNumber);
int[] result = {x+1, i+1};
return result;
}
hashMap.put(numbers[i], i);
}
return null;
}


上一篇
[Day06] 30天挑戰演算法 - 一枝獨秀
下一篇
[Day08] 30 天挑戰演算法 - 判斷二元搜尋樹
系列文
連續30天,挑戰演算法30

2 則留言

0
海綿寶寶
iT邦超人 1 級 ‧ 2014-10-07 08:36:04

pajace2001提到:
記得多年以前看過一部電視劇「保鏢」,其中有一幕是這樣說的:

有沒有這麼大年紀呀
你看過這麼多年前的電視劇
汗

0
pajace2001
iT邦研究生 1 級 ‧ 2014-10-07 08:52:14

那其實是我小時候啦 XD...... 新版的介面好不習慣阿~~
antijava 大,請問你是怎麼貼圖阿~ 我都找不到怎麼貼

我要留言

立即登入留言