摘要

本文圍繞 LeetCode 259 題“較小的三數之和”，通過 Swift 給出兩種解法，并結合雙指針的優化思路，講清楚這類“數組 + 條件組合”類題目常見的解決套路。同時附上可運行 Demo，幫助你快速上手并掌握三數問題的變種場景。

描述

題目要求：
給定一個整數數組 nums，以及一個目標值 target，請你統計在所有不同的三元組 (i, j, k) 中，滿足：

nums[i] + nums[j] + nums[k] < target 且 i < j < k

的組合總數，并返回這個值。

示例 1：

輸入: nums = [-2, 0, 1, 3], target = 2  
輸出: 2  
解釋: 滿足的組合有 (-2, 0, 1) 和 (-2, 0, 3)

示例 2：

輸入: nums = [], target = 0  
輸出: 0

示例 3：

輸入: nums = [0], target = 0  
輸出: 0

題解答案（Swift）

這道題其實是“三數和”的一個變種，只不過目標變成了 < target，不再是 == 0。最直觀的解法是暴力三重循環，但效率感人，時間復雜度是 O(n3)。這里我們采用排序 + 雙指針的思路，降低時間復雜度。

題解代碼分析

func threeSumSmaller(_ nums: [Int], _ target: Int) -> Int {let sorted = nums.sorted()var count = 0for i in 0..<sorted.count - 2 {var left = i + 1var right = sorted.count - 1while left < right {let sum = sorted[i] + sorted[left] + sorted[right]if sum < target {// 所有 [left, right) 的組合都滿足條件count += right - leftleft += 1} else {right -= 1}}}return count
}

示例測試及結果

print(threeSumSmaller([-2, 0, 1, 3], 2))  // 輸出：2
print(threeSumSmaller([], 0))            // 輸出：0
print(threeSumSmaller([0], 0))           // 輸出：0
print(threeSumSmaller([1, 2, 3, 4, 5], 9)) // 輸出：4

解釋：

• 對于 [1,2,3,4,5]，滿足三數和 < 9 的組合有：
  • 1+2+3=6
  • 1+2+4=7
  • 1+2+5=8
  • 1+3+4=8

共 4 個。

時間復雜度

• 排序需要 O(n log n)
• 主循環是 O(n2)

整體時間復雜度：O(n2)，比暴力三重循環好很多。

空間復雜度

• 排序用了額外空間（可能是快排的棧）
• 主要是常數級別的變量，沒有使用額外數組

空間復雜度：O(1)（不考慮排序時的棧開銷）

總結

這題其實屬于“三數問題”的系列題目，只不過目標條件從 == target 變成了 < target。一旦習慣了排序 + 雙指針的套路，這類題目處理起來就非常順手了。

也建議大家嘗試思考下另外兩個方向：

• 如果是 > 怎么辦？
• 如果不能排序怎么辦？

另外也可以思考怎么把這類題目封裝成通用的“多數和小于目標”的函數，能提升在面試中的發揮空間。