如何降低JavaScript中计算用户总存款的时间复杂度？

问题描述 #

我有两个对象数组 users 和 deposits：

const users = [
    {
        _id: 1,
        username: 'tajmirul',
        email: 'tajmirul@gmail.com',
    },
    {
        _id: 2,
        username: 'tajmirul2',
        email: 'tajmirul2@gmail.com',
    },
];

const deposits = [
    {
        _id: 1,
        userId: 1,
        amount: 250,
    },
    {
        _id: 2,
        userId: 1,
        amount: 500,
    },
];

需要计算每个用户的总存款并更新 users 数组，最终效果如下：

// 修改后的 users 数组
[
    {
        _id: 1,
        username: 'tajmirul',
        deposit: 750,
    },
    {
        _id: 2,
        username: 'tajmirul2',
        deposit: 0,
    }
]

我当前用嵌套循环实现的代码时间复杂度是 O(m * n)（m为用户数量，n为存款记录数量）：

users.forEach((user, index) => {
    deposits.forEach(deposit => {
        if (user._id === deposit.userId) {
            if (users[index].deposit) {
                users[index].deposit += deposit.amount;
            } else {
                users[index].deposit = deposit.amount;
            }
        }
    });
});

有没有办法降低时间复杂度？

优化方案：哈希表预处理存款数据 #

当然可以，核心是把嵌套循环拆成两次线性遍历，用哈希表（对象或Map）提前统计好每个用户的存款总额，时间复杂度能降到 O(m + n)，具体实现如下：

步骤1：统计每个用户的总存款 #

先遍历一次deposits数组，用对象记录每个用户的累计存款：

const depositTotals = {};
deposits.forEach(deposit => {
    const userId = deposit.userId;
    // 有记录就累加，无记录则初始化为当前金额
    depositTotals[userId] = (depositTotals[userId] || 0) + deposit.amount;
});

步骤2：更新用户数组 #

再遍历一次users数组，给每个用户赋值对应的存款总额（没有存款的设为0）：

users.forEach(user => {
    user.deposit = depositTotals[user._id] || 0;
    // 如果不需要保留email字段，可执行：delete user.email;
});

这种方法在数据量较大时优势非常明显，比如当用户数和存款记录数都达到上千条时，O(m+n)的效率会远高于O(m*n)的嵌套循环。

内容的提问来源于stack exchange，提问作者Tajmirul Islam