摘要

這道題其實就是經典的 “兩個水壺問題”，你可能在電影《虎膽龍威3》里見過，布魯斯·威利斯用兩個水壺精確量出 4 升水來解除炸彈。這題就是把那個場景搬到了編程世界里。

我們的目標是：給定兩個水壺的容量，看看能不能通過倒水、裝滿、倒空等操作，剛好得到指定的 target 升水。

描述

題目設定：

• 有兩個水壺，容量分別是 x 和 y 升。

• 水無限供應。

• 操作允許：

  1. 把任意一個水壺裝滿
  2. 把任意一個水壺清空
  3. 把一個水壺里的水倒進另一個水壺，直到前者空或者后者滿

問題：能不能正好量出 target 升？

示例 1

輸入: x = 3, y = 5, target = 4
輸出: true

示例 2

輸入: x = 2, y = 6, target = 5
輸出: false

示例 3

輸入: x = 1, y = 2, target = 3
輸出: true

題解答案

其實解法有兩個方向：

1. 數學解法（最大公約數 GCD）

   • 經典定理：只要 target <= x + y，并且 target 是 gcd(x, y) 的倍數，就能得到。
   • 這就是數論里的貝祖定理。
   • 這個方法非常簡潔高效。

2. 模擬解法（BFS/DFS 搜索所有可能的狀態）

   • 模擬真實倒水過程，嘗試所有可能的壺水量組合，看是否能達到 target。
   • 更直觀，但效率會差一些。

我這里用 Swift 先寫 數學解法，然后再在分析里擴展到模擬解法。

題解代碼分析

下面是 Swift 的數學解法代碼：

import Foundationclass Solution {func canMeasureWater(_ x: Int, _ y: Int, _ target: Int) -> Bool {// 如果目標超過兩個水壺加起來的容量，直接不可能if target > x + y {return false}// 如果剛好等于總容量，也行if target == x + y {return true}// 如果目標是 0 也 trivially 成立if target == 0 {return true}// 使用最大公約數判斷return target % gcd(x, y) == 0}// 求最大公約數（輾轉相除法）private func gcd(_ a: Int, _ b: Int) -> Int {if b == 0 { return a }return gcd(b, a % b)}
}// MARK: - Demo 演示
let solution = Solution()print("示例1: \(solution.canMeasureWater(3, 5, 4))") // true
print("示例2: \(solution.canMeasureWater(2, 6, 5))") // false
print("示例3: \(solution.canMeasureWater(1, 2, 3))") // true

代碼拆解

1. 判斷邊界情況：

   • 如果 target 比兩個壺加起來還大，那不可能。
   • 如果 target 等于總容量，那就直接可以倒滿。
   • 如果 target = 0，也 trivially 成立。

2. 用最大公約數 GCD 判斷：

   • 數學原理是：能倒出的水量一定是 gcd(x, y) 的倍數。
   • 所以只要 target % gcd(x, y) == 0，就能實現。

3. Demo 測試：
   三個示例跑完結果都正確。

示例測試及結果

運行結果：

示例1: true
示例2: false
示例3: true

再自己加幾個測試：

print(solution.canMeasureWater(6, 10, 8)) // true，因為 gcd(6,10)=2，8是2的倍數
print(solution.canMeasureWater(6, 10, 7)) // false，因為 gcd=2，7不是倍數
print(solution.canMeasureWater(4, 4, 8))  // true，兩個壺一起裝滿就行

時間復雜度

• 主要就是求一次最大公約數，時間復雜度 O(log(min(x, y)))。
• 非常快。

空間復雜度

• 除了遞歸棧，幾乎沒有額外空間，復雜度是 O(1)。

總結

這題其實一眼看上去像 BFS/DFS 的模擬搜索題，但背后藏著一個非常優雅的數學結論。
核心公式就是：target % gcd(x, y) == 0 且 target <= x + y。

在實際生活中，這種場景也經常遇到，比如：

• 你有兩個量杯，要量出指定的水。
• 工廠配料時，用不同規格的容器去配比原料。
• 甚至調酒的時候，也能用這個方法。

如果你喜歡更直觀的解法，也可以用 BFS 來寫，把 (a, b) 表示當前兩個壺的狀態，然后不斷倒水直到找到目標。這個解法更貼近真實操作，但效率會差一些。