四數總和 / k 數總和

從兩數到三數總和,我們可以推敲出四數:

  • 四數 = 輪詢三數 + 三數輪詢二數

那麼以此類推了話,k 數核心 (虛擬碼):

kSum = for num in nums: kSum(nums, k - 1, target-num) if k > 2 else twoSum(nums, target-num)

p.s. 沒檢查 k < 2 的邊界問題

時間複雜度:

  • twoSum: sort O(nlogn) + twoSum O(n)
  • threeSum: sort O(nlogn) + O(n) * twoSum O(n)
  • fourSum: sort O(nlogn) + O(n) * threeSum O(n²)
  • kSum: sort O(nlogn) + O(n^k-1)

答案:

可最佳化的部分有:如何沿用 result 避免重複建構