多人消费费用均摊后互相转账金额计算的JavaScript实现咨询

可搜索的关键词 #

如果需要查找相关资料，可以搜索以下关键词：

• 多人债务清算算法
• 最小转账次数均摊算法
• 最优分账结算算法

实现思路 #

你已完成的差额计算是正确的，首先明确差额定义：你代码中difference = 人均应付金额 - 个人实际花费金额

• 差值为正：该用户实际支出少于应支出，需要向外转出对应金额
• 差值为负：该用户实际支出多于应支出，需要收回对应金额（金额为差值的绝对值）
  接下来用贪心算法计算转账关系即可，步骤如下：

1. 拆分两个队列：
   • 付款队列：所有差值为正的用户，存储用户姓名和待转出总金额
   • 收款队列：所有差值为负的用户，存储用户姓名和待收回总金额
2. 双指针遍历匹配转账关系：
   每次取当前付款队列的第一个付款人，和当前收款队列的第一个收款人，取两者待处理金额的最小值作为本次转账金额，生成转账记录后更新两者剩余金额：

• 付款人待转出金额为0时，移动付款指针到下一个付款人
• 收款人待收回金额为0时，移动收款指针到下一个收款人
• 重复操作直到两个队列所有用户的金额都清0
  该算法可以保证总转账次数最少，适配所有复杂场景，包括一人向多人转账、多人向一人转账的情况。

参考代码（适配你的现有数据） #

// 入参为你已经计算完difference属性的persons数组
function calculateTransferRecords(persons) {
  // 拆分付款、收款队列，如需输出和示例完全一致的顺序，可在此处给队列增加排序规则
  const payers = persons
    .filter(item => item.difference > 0)
    .map(item => ({
      name: item.name.charAt(0).toUpperCase() + item.name.slice(1),
      amount: item.difference
    }))
  const receivers = persons
    .filter(item => item.difference < 0)
    .map(item => ({
      name: item.name.charAt(0).toUpperCase() + item.name.slice(1),
      amount: Math.abs(item.difference)
    }))
  
  const transferRecords = []
  let payIndex = 0
  let receiveIndex = 0

  while (payIndex < payers.length && receiveIndex < receivers.length) {
    const currentPayer = payers[payIndex]
    const currentReceiver = receivers[receiveIndex]
    const transferAmount = Math.min(currentPayer.amount, currentReceiver.amount)

    // 生成转账记录
    transferRecords.push(`${currentPayer.name} to ${currentReceiver.name}: ${transferAmount}`)

    // 更新剩余待处理金额
    currentPayer.amount -= transferAmount
    currentReceiver.amount -= transferAmount

    // 付款人已付清，移动指针
    if (currentPayer.amount === 0) {
      payIndex++
    }
    // 收款人已收齐，移动指针
    if (currentReceiver.amount === 0) {
      receiveIndex++
    }
  }

  return transferRecords
}

// 调用测试
const result = calculateTransferRecords(persons)
console.log(result)

如果需要和你给出的示例输出完全一致，只需要给付款队列、收款队列加上自定义排序规则即可，不同排序方式只会调整转账匹配顺序，不影响最终平账结果。

内容的提问来源于stack exchange，提问作者Homer Pitt