- 注意nums为空时的边界条件。

* 语言支持：JS，Python，C++

if(size==0) return 0;

C++ Code:

class Solution {

public:

int removeDuplicates(vector<int>& nums) {

if(nums.empty()) return 0;

int fast,slow;

fast=slow=0;

while(fast!=nums.size()){

if(nums[fast]==nums[slow]) fast++;

else {

slow++;

nums[slow]=nums[fast];

fast++;

}

}

return slow+1;

}

};

两个水壶的水我们考虑成状态，然后我们不断进行倒的操作，改变状态。那么初始状态就是（0 0） 目标状态就是 （any, z）或者 (z, any)，其中any 指的是任意升水。

已题目的例子，其过程示意图，其中括号表示其是由哪个状态转移过来的：

0 0

3 5(0 0) 3 0 (0 0 )0 5(0 0)

3 2(0 5) 0 3(0 0)

0 2(3 2)

2 0(0 2)

2 5(2 0)

3 4(2 5) bingo

class Solution:

def canMeasureWater(self, x: int, y: int, z: int) -> bool:

if x + y < z:

return False

queue = [(0, 0)]

seen = set((0, 0))

while(len(queue) > 0):

a, b = queue.pop(0)

if a ==z or b == z or a + b == z:

return True

states = set()

states.add((x, b))

states.add((a, y))

states.add((0, b))

states.add((a, 0))

states.add((min(x, b + a), 0 if b < x - a else b - (x - a)))

states.add((0 if a + b < y else a - (y - b), min(b + a, y)))

for state in states:

if state in seen:

continue;

queue.append(state)

seen.add(state)

return False

**复杂度分析**

- 时间复杂度：由于状态最多有$O((x + 1) * (y + 1))$ 种，因此总的时间复杂度为$O(x * y)$。

- 空间复杂度：我们使用了队列来存储状态，set 存储已经访问的元素，空间复杂度和状态数目一致，因此空间复杂度是$O(x * y)$。

上面的思路很直观，但是很遗憾这个算法在 LeetCode 的表现是 TLE(Time Limit Exceeded)。不过如果你能在真实面试中写出这样的算法，我相信大多数情况是可以过关的。

我们来看一下有没有别的解法。实际上，上面的算法就是一个标准的 BFS。如果从更深层次去看这道题，会发现这道题其实是一道纯数学问题，类似的纯数学问题在 LeetCode 中也会有一些，不过大多数这种题目，我们仍然可以采取其他方式 AC。那么让我们来看一下如何用数学的方式来解这个题。

因此这道题可以完全转化为`裴蜀定理`。还是以题目给的例子`x = 3, y = 5, z = 4`，我们其实可以表示成`3 * 3 - 1 * 5 = 4`, 即`3 * x - 1 * y = z`。我们用a和b分别表示3

升的水壶和5升的水壶。那么我们可以：

- 倒满a（**1**）

- 将a倒到b

- 再次倒满a（**2**）

- 再次将a倒到b（a这个时候还剩下1升）

- 倒空b（**-1**）

- 将剩下的1升倒到b

- 将a倒满（**3**）

- 将a倒到b

- b此时正好是4升

上面的过程就是`3 * x - 1 * y = z`的具体过程解释。

**也就是说我们只需要求出x和y的最大公约数d，并判断z是否是d的整数倍即可。**

代码支持：Python3，JavaScript

Python Code：

class Solution:

def canMeasureWater(self, x: int, y: int, z: int) -> bool:

if x + y < z:

return False

if (z == 0):

return True

if (x == 0):

return y == z

if (y == 0):

return x == z

def GCD(a, b):

smaller = min(a, b)

while smaller:

if a % smaller == 0 and b % smaller == 0:

return smaller

smaller -= 1

return z % GCD(x, y) == 0

JavaScript：

实际上求最大公约数还有更好的方式，比如辗转相除法：

def GCD(a, b):

if b == 0: return a

return GCD(b, a % b)

**复杂度分析**

- 时间复杂度：$O(log(max(a, b)))$

- 空间复杂度：空间复杂度取决于递归的深度，因此空间复杂度为 $O(log(max(a, b)))$

- 数论

- 裴蜀定理

更多题解可以访问我的LeetCode题解仓库：https://github.com/azl397985856/leetcode 。 目前已经接近30K star啦。

大家也可以关注我的公众号《脑洞前端》获取更多更新鲜的LeetCode题解