如何以O(n)时间复杂度计算用户消费后的钱包剩余金额

API 探路者

2026-9-29

O(n)复杂度实现方案

核心思路

要实现线性时间复杂度，核心是避免嵌套循环查表，通过哈希映射（Map/普通对象）把查找操作的耗时降到O(1)，仅需要对三个数组各做一次遍历即可：

第一次遍历产品数组，生成商品名称-单价的映射表
第二次遍历钱包数组，生成用户名-初始余额的映射表，同时初始化用户名-总消费的统计映射
第三次遍历购买记录数组，直接查表完成消费累加、信贷存入、余额扣除的逻辑
总时间复杂度为O(p+u+o)（p为产品数、u为用户数、o为购买记录数），符合要求的O(n)标准。

实现代码

// 1. 生成商品价格映射表
const priceMap = new Map(product.map(item => [item.name, item.price]))

// 2. 初始化用户余额、总消费映射表
const userBalance = new Map()
const userTotalConsume = new Map()
purse.forEach(user => {
  userBalance.set(user.name, user.cash)
  userTotalConsume.set(user.name, 0)
})

// 3. 遍历购买记录完成计算
purchases.forEach(record => {
  const username = record.name
  const itemPrice = priceMap.get(record.item)
  // 累加用户总消费
  userTotalConsume.set(username, userTotalConsume.get(username) + itemPrice)
  // 有信贷则先存入钱包
  if (record.credit) {
    userBalance.set(username, userBalance.get(username) + record.credit)
  }
  // 扣除本次消费金额
  userBalance.set(username, userBalance.get(username) - itemPrice)
})

// 如需转为普通对象使用可调用：
// const consumeResult = Object.fromEntries(userTotalConsume)
// const balanceResult = Object.fromEntries(userBalance)