iT邦幫忙

2022 iThome 鐵人賽

DAY 30
0
自我挑戰組

30天演算法解題系列 第 30

Day 30:four number sum

  • 分享至 

  • xImage
  •  

problem

輸入為一陣列及一整數 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 sumthree 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,還會需要考慮兩個問題:

  1. 可能會有不同數字組合得出相同的 P/ Q
    例如 [7, 6, 4, -1, 1, 2] 中,4 + 2 和 7 + (-1) 都是 6,所以在 hash table 中可能需記成這種形式:
    {
     6: [[4, 2], [7, -1]]
    }
  2. 要避免重複計算
    若 array = [7, 6, 4, -1, 1, 2],target = 16
    hash table 中可能會記錄如下,這樣就會得出兩組相加為 16 的解,但其實是同樣的四個數字以不同方式排列,要避免這樣的情形。
    {
     13: [[7, 6]],
     3: [[4, -1]],
     10: [[6, 4]],
     6: [[7, -1]]
    }

綜合以上,具體的步驟是:

  1. 迴圈過每個數字 i,對 i 進行以下步驟 2、3,
  2. 以一個迴圈看 i 後面的所有數字 j,並計算 i + j == P。檢查(target - P) 是否有在 hash table 中,如果有,代表找到解,將所有組合推進結果陣列中。如果沒有,不將 P 加入,繼續看下個數字。
  3. 以一個迴圈看 i 前面的所有數字 k,並計算 i + k == Q。檢查 Q 是否有在 hash table 中,如果有,將 [i, k] 的組合加入其中。如果沒有,新增 Q 及組合進去。
  4. 最後回傳結果陣列。

統整一下:
步驟 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;
}

以上就是今年鐵人賽的最後一題。以這一題作為結尾,也很能表達這個月記錄演算法解題的心情,就是當碰到有點複雜又巧妙的方法時,其實常覺得一切只可意會,越多文字解釋反而越講不清楚。

但即便很難表達,這條路上還是有很多老師、同伴每日不斷嘗試用更簡潔明瞭的方法描述演算法,這和不斷優化演算法本身應該算是一樣的修練,對於他們的貢獻真心感謝。


上一篇
Day 29:invert binary tree
系列文
30天演算法解題30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言