輸入為一陣列及一整數 target,陣列不為空陣列,且元素不重複。如果陣列中有四個數字相加等於 target,以雙層陣列 (two-dimentional array) 的結構回傳所有數組 (順序不拘),否則回傳空陣列。
sample input:
array = [7, 6, 4, -1, 1, 2]
target = 16
sample output:
[
[7, 6, 4, -1],
[7, 6, 1, 2]
]
開賽的時候寫了 two number sum 和 three number sum 問題,有很多有趣的解法,現在到了比賽最後,就以 four number sum 做結。
假設任意四個數字 x, y, z, k,如果將它們分為兩個一組,則四數總和可以想成兩組數字總和 (x + y) + (z + k)。也就是說如果找到陣列中所有的兩數字和,可以將這個問題簡化為 two number sum 的變化型。
two number sum 中有使用 hash table 的解法,過程中對於每個數字利用 (target - 數字) 進行查找,並將數字儲存。而這一題假設 x + y 為 P,z + k 為 Q,可以嘗試同樣的方法,查找 (target - P),並記錄 Q,有找到符合的解再進一步記錄四個數字。不過相較於單純的 two number sum,還會需要考慮兩個問題:
綜合以上,具體的步驟是:
統整一下:
步驟 2 只會檢查是否有解,不加入 hash table,
步驟 3 只會加入 hash table,不檢查是否找到解。
之所以在步驟 2 不加入 P,步驟 3 才加入 Q,是要在組合第二次出現時才加入 hash table,以此來避免重複。
例如 array = [7, 6, 4, -1, 1, 2],target = 16
[7, 6] 這個組合,會在迴圈 i 為 6 的時候才記錄,就不會 7 和 6 的時候各記了一次。並且 [7, 6, 4, -1] 這組解會迴圈到 4 的時候才找到,不會在 i 為 7 和 6 的時候就反覆記錄。
n 為輸入陣列長度,
time: O(n^2) 這是大部分情況的時間,來自外層與內層的迴圈。可能會有的特殊情況是 hash table 中某個組合特別多 (如下)。碰到這種情況時,遍歷這些組合加入結果陣列就會花比較多時間,所以最遭情況的時間會不止 n^2 。
array = [-4, -3, -2, -1, 1, 2, 3, 4],target = 0
hash = {
0: [[-4, 4], [-3, 3], [-2, 2], [-1, 1]],
...
}
space: O(n^2) 因為會記錄 n^2 種數字和。
function fourNumberSum(array, target) {
const results = [];
const pairSums = {};
for (let i = 0; i < array.length -1; i++) {
for (let j = i + 1; j < array.length; j++) {
const diff = target - (array[i] + array[j]);
if (pairSums[diff]) {
for (const pair of pairSums[diff]) {
results.push([...pair, array[i], array[j]]);
}
}
}
for (let k = 0; k < i; k++) {
const sum = array[i] + array[k];
if (!pairSums[sum]) {
pairSums[sum] = [[array[i], array[k]]];
} else {
pairSums[sum].push([array[i], array[k]]);
}
}
}
return results;
}
以上就是今年鐵人賽的最後一題。以這一題作為結尾,也很能表達這個月記錄演算法解題的心情,就是當碰到有點複雜又巧妙的方法時,其實常覺得一切只可意會,越多文字解釋反而越講不清楚。
但即便很難表達,這條路上還是有很多老師、同伴每日不斷嘗試用更簡潔明瞭的方法描述演算法,這和不斷優化演算法本身應該算是一樣的修練,對於他們的貢獻真心感謝。