LLD 案例：Splitwise 分账

Splitwise（多人记账分摊）这道题的代码量不大，考点集中在钱算得对不对：怎么分才能一分不差，余额怎么算，几个人互相欠钱时怎么用最少的转账结清。

需求澄清

功能需求

1. 用户可以建群（室友、旅行团），群里记录支出。
2. 每笔支出有一个付款人和若干参与人，分摊方式有三种：平均、指定金额、按百分比。
3. 查看群内每个人的净余额：别人欠他多少，或者他欠别人多少。
4. 记录还款：A 还给 B 一笔钱。
5. “简化债务”：给出一组转账，让所有人结清，转账次数尽量少。

非功能需求

• 金额精确到分，每笔支出拆出来的份额之和必须等于总额。
• 历史可追溯：任何余额都能从支出和还款记录里重新算出来。

明确不做：多币种（放到扩展讨论）、真实支付。

核心类

classDiagram
  accTitle: Splitwise 类图：群组、支出、还款与分摊规则
  class Group {
    -List members
    -List expenses
    -List payments
    +addExpense(Expense e)
    +settle(String from, String to, int cents)
    +balances() Map
  }
  class Expense {
    -String id
    -String paidBy
    -int amount
    -Map shares
  }
  class Payment {
    -String from
    -String to
    -int cents
  }
  class SplitRule {
    <<interface>>
    +shares(int amount) Map
  }
  class DebtSimplifier {
    +simplify(Map net) List
  }
  Group "1" *-- "many" Expense
  Group "1" *-- "many" Payment
  Group ..> SplitRule : builds shares
  Group ..> DebtSimplifier
  SplitRule <|.. EqualSplit
  SplitRule <|.. ExactSplit
  SplitRule <|.. PercentSplit

用到的设计模式

• 策略模式：三种分摊方式输入不同，输出都是“每人应摊多少分”。Expense 里只存算好的份额，不存分摊方式的参数，余额计算就不需要关心分摊方式。
• 不可变的流水：Expense 和 Payment 只追加、不修改。余额是从流水算出来的结果，可以缓存，但不是数据源。

分摊：一分钱也不能丢

100 元三人平分，每人 33.33 元，加起来是 99.99 元，丢了 1 分钱。规则是先整除，余数按固定顺序一分一分地分出去：前一个人 33.34 元，后两个人 33.33 元。顺序要固定（比如按参与人列表的顺序），重新计算时结果才一致。

按百分比分摊时也有同样的问题，而且百分比常带小数（33.33%）。用“万分之一”的整数（3333 表示 33.33%）就能避开浮点数；先向下取整，剩下的几分钱给小数部分最大的几个人：

def split_equal(amount: int, people: list[str]) -> dict[str, int]:
    base, extra = divmod(amount, len(people))
    return {p: base + (1 if i < extra else 0) for i, p in enumerate(people)}


def split_exact(amount: int, amounts: dict[str, int]) -> dict[str, int]:
    if sum(amounts.values()) != amount:
        raise ValueError("amounts must add up to the total")
    return dict(amounts)


def split_percent(amount: int, basis_points: dict[str, int]) -> dict[str, int]:
    """basis_points: hundredths of a percent, adding up to 10_000 (3333 = 33.33%)."""
    if sum(basis_points.values()) != 10_000:
        raise ValueError("percentages must add up to 100")
    shares = {p: amount * bp // 10_000 for p, bp in basis_points.items()}
    left = amount - sum(shares.values())  # fewer cents than people
    by_remainder = sorted(basis_points, key=lambda p: amount * basis_points[p] % 10_000, reverse=True)
    for p in by_remainder[:left]:
        shares[p] += 1
    return shares

核心代码

import heapq
from collections import defaultdict
from dataclasses import dataclass


@dataclass(frozen=True)
class Expense:
    id: str
    paid_by: str
    amount: int             # cents
    shares: dict[str, int]  # who owes how much of it


class Group:
    def __init__(self):
        self.expenses: list[Expense] = []
        self.payments: list[tuple[str, str, int]] = []  # (from, to, cents)

    def add_expense(self, e: Expense) -> None:
        if sum(e.shares.values()) != e.amount:
            raise ValueError("shares must add up to the amount")
        self.expenses.append(e)

    def settle(self, frm: str, to: str, cents: int) -> None:
        self.payments.append((frm, to, cents))

    def balances(self) -> dict[str, int]:
        net = defaultdict(int)  # > 0: is owed money, < 0: owes
        for e in self.expenses:
            net[e.paid_by] += e.amount
            for user, share in e.shares.items():
                net[user] -= share
        for frm, to, cents in self.payments:
            net[frm] += cents
            net[to] -= cents
        return dict(net)


def simplify(net: dict[str, int]) -> list[tuple[str, str, int]]:
    """Largest debtor pays largest creditor until everyone is even: at most n - 1 transfers."""
    creditors = [(-v, u) for u, v in net.items() if v > 0]
    debtors = [(v, u) for u, v in net.items() if v < 0]
    heapq.heapify(creditors)
    heapq.heapify(debtors)
    transfers = []
    while creditors and debtors:
        c, cu = heapq.heappop(creditors)  # -c: what cu is owed
        d, du = heapq.heappop(debtors)    # -d: what du owes
        pay = min(-c, -d)
        transfers.append((du, cu, pay))
        if -c > pay:
            heapq.heappush(creditors, (c + pay, cu))
        if -d > pay:
            heapq.heappush(debtors, (d + pay, du))
    return transfers

balances 有一个不变量：所有人的净余额加起来恒等于 0。每笔支出给付款人加了多少，就从参与人身上减了多少；还款也一样。测试时可以把这条当断言。

简化债务

净余额算出来之后，谁欠谁已经不重要了，只需要让负数的人付钱给正数的人。上面的贪心每次让欠得最多的人付给被欠得最多的人，金额取两者较小值，所以每一轮至少有一个人结清。n 个人最多需要 n − 1 笔转账。

这个结果不保证转账次数最少。比如有两组人彼此正好能内部结清，最优解会利用这一点，贪心未必能发现。求真正的最少转账次数是 NP 难问题（相当于把人分成尽量多个净额为 0 的小组），面试里说清楚“贪心给出不超过 n − 1 笔的结果，最优解代价太高”就够了。

扩展讨论

• 修改和删除支出：不改原记录，追加一条“作废”记录再加一条新支出，或者给支出加版本号。余额随之重新计算。
• 多币种：每笔支出记录原币种和金额，余额按币种分别计算；要换算成一种货币结算时，记录当时使用的汇率。
• 大群的性能：每次都从全部流水重算会越来越慢，可以维护一个按群缓存的净余额，每追加一条流水就增量更新，定期用全量重算校验。
• 多个付款人：一笔支出由两个人一起付，把 paid_by 换成“谁付了多少”的映射，余额公式不变。