٩꒰｡•◡•｡꒱۶
嗨，我是wec，今天是DAY 18。

🔎 題目難度與描述

難度：MEDIUM

題目描述：

給定四個整數數組nums1,nums2,nums3,nums4，數組長度都是n，找出所有滿足 a + b + c + d = 0 的組合數量，其中a、b、c和d分別來自nums1,nums2,nums3,nums4。

🔎 解題思路＆程式碼

1️⃣ 雜湊表

第1步： 先將nums1和nums2的所有兩兩之和存到一個雜湊表中，然後記錄每個和出現的次數。
第2步： 然後遍歷nums3和nums4，查找-(c + d) 是否在雜湊表中，如果在就說明之前的和可以跟現在的和湊成0。最後把雜湊表中記錄的次數加到結果裡。
程式碼：

def four_sum_count(nums1, nums2, nums3, nums4)
  count = Hash.new(0)

  nums1.each do |a|
    nums2.each do |b|
      count[a + b] += 1
    end
  end

  result = 0

  nums3.each do |c|
    nums4.each do |d|
      result += count[-(c + d)]
    end
  end

  result
end

🔎 總結

時間複雜度

雜湊表： 時間複雜度為O(n²)，n為組數長度。
➡️ 這題的關鍵在於利用雜湊表來減少不必要的計算，透過將問題分解成兩個22的組合做分開處理，我們只需記錄前兩組數的和，然後檢查後兩組數的和的負數是否存在雜湊表裡。如果沒有分開看，時間複雜度就會來到驚人的O(n⁴)，所以12一組34一組存到雜湊表裡的方法大幅提高了效率!!ฅʕ◍˙Ⱉ˙◍ʔฅ

那麽，以上就是今天的內容！

相信IT人動腦時都要吃點東西，所以今天邊寫邊吃醬油糰子(加花生粉)。
明天要說：Ruby精選刷題！Medium路跑D-11(>∀･)⌒☆