LeetCode 465 最优账单平衡

摘要

《最优账单平衡》这道题，很多人第一次看到都会有点懵：
不就是转账吗，为什么会是困难题？

真正难的地方不在“算钱”，而在于如何用最少的转账次数，把一堆复杂的债务关系彻底清零。
这类问题在现实中非常常见，比如：

• 多人 AA 聚餐之后的结算
• 团队项目里垫资、报销、代付
• 公司内部多部门费用对冲

题目本身不复杂，但如果直接模拟转账，很容易陷入组合爆炸。
正确的解法核心只有一句话：

先把问题化简，再用回溯暴力，但要暴力得聪明。

描述

题目给了我们一组交易transactions，每一条形如：

[from, to, amount]

表示：
from给to转了amount的钱。

最终目标是：
在不改变每个人最终盈亏结果的前提下，用最少的转账次数，把所有人的账清干净。

有几个关键约束需要先想清楚：

1. 不关心原始交易顺序
2. 只关心“每个人最终是多收了钱，还是多付了钱”
3. 转账次数越少越好，金额大小无所谓

换句话说，我们不是要“复现原交易”，而是要重排债务关系。

题解答案

整体思路可以分成两步。

计算每个人的净资产

我们先不管怎么转账，只统计结果：

• 转出的钱：记为负数
• 转入的钱：记为正数

最后每个人只会剩下一个数：

• 正数：别人欠他钱
• 负数：他欠别人钱
• 0：已经结清，可以直接忽略

这一步非常关键，它能把问题规模大幅缩小。

在净资产数组上做最少匹配

接下来就变成了一个更抽象的问题：

给你一组正负数，正数和负数总和为 0，
用最少的“配对抵消”次数，让所有数都变成 0。

这个问题非常适合用回溯 + 剪枝来解决：

• 每次找一个还没清零的债务
• 尝试和后面符号相反的债务进行抵消
• 把这一步算作一次转账
• 递归处理剩余部分
• 取最小次数

题解代码分析

下面是完整 Swift 实现，逻辑清晰、可以直接运行。

classSolution{funcminTransfers(_transactions:[[Int]])->Int{varbalance=[Int:Int]()// 统计每个人的净资产fortintransactions{letfrom=t[0]letto=t[1]letamount=t[2]balance[from,default:0]-=amount balance[to,default:0]+=amount}// 只保留不为 0 的债务vardebts=balance.values.filter{$0!=0}returndfs(&debts,0)}privatefuncdfs(_debts:inout[Int],_start:Int)->Int{// 跳过已经结清的whilestart<debts.count&&debts[start]==0{returndfs(&debts,start+1)}ifstart==debts.count{return0}varminCount=Int.maxforiin(start+1)..<debts.count{// 只尝试符号相反的进行抵消ifdebts[start]*debts[i]<0{letoriginal=debts[i]debts[i]+=debts[start]minCount=min(minCount,1+dfs(&debts,start+1))debts[i]=original// 剪枝：如果正好抵消，没必要再试别的iforiginal+debts[start]==0{break}}}returnminCount}}

核心逻辑拆解一下

为什么可以忽略已经为 0 的人？

因为他们已经“账平了”，不需要再参与任何转账。
这一步对性能提升非常明显。

为什么只找符号相反的？

• 一个是欠钱（负数）
• 一个是收钱（正数）

只有这样才能发生真实有效的“抵消”。
两个正数或者两个负数，永远解决不了问题。

剪枝为什么成立？

iforiginal+debts[start]==0{break}

这表示：
当前这次配对已经是完美抵消，再继续尝试别的组合，只会增加转账次数，不可能更优。

示例测试及结果

示例 1

letsolution=Solution()lettransactions=[[0,1,10],[2,0,5]]print(solution.minTransfers(transactions))

分析过程

• 0：-10 + 5 = -5
• 1：+10
• 2：-5

债务数组变成：

[-5, 10, -5]

最优方案：

• 1 给 0 转 5
• 1 给 2 转 5

总共2 次转账

输出：

2

示例 2

lettransactions=[[0,1,10],[1,0,10]]print(solution.minTransfers(transactions))

两笔交易完全抵消，所有人最终余额都是 0。

输出：

0

时间复杂度

这道题本质上是一个NP 难问题。

• 最坏情况下，需要尝试所有债务组合
• 回溯的时间复杂度接近O(n!)

但题目限制了参与人数，一般不会超过 12 个非零债务节点。
再加上大量剪枝，实际运行非常快。

空间复杂度

主要消耗在：

• debts数组
• 递归调用栈

空间复杂度为：

O(n)

总结

《最优账单平衡》这道题的价值不在于“写代码有多复杂”，而在于建模能力：

1. 把原始交易压缩成“净资产”
2. 把业务问题抽象成“正负数抵消”
3. 用回溯解决“最少操作次数”问题