LeetCode 2623. Memoize代码测试用例报错，求错误原因排查

题目要求 #

给定一个函数fn，返回它的记忆化版本。记忆化函数不会对相同的输入调用两次，而是返回缓存的值。可输入的函数有三种：

• sum：接收两个整数a和b，返回a+b；
• fib：接收单个整数n，n<=1时返回1，否则返回fib(n-1)+fib(n-2)；
• factorial：接收单个整数n，n<=1时返回1，否则返回factorial(n-1)*n。

我的JavaScript实现 #

/**
 * @param {Function} fn
 * @return {Function}
 */
function memoize(fn) {
    let arr = [];
    let result = [];
    return function (...args) {
        if (!(arr.toString().match(args.toString()))) {
            arr.push(args);
            let val = fn(...args);
            result.push(val);
            return val;
        } else {
            for (let i = 0; i < arr.length; i++) {
                if (arr[i].toString() === args.toString()) {
                    return result[i];
                }
            }
        }
    }
}

/** 
 * LeetCode提供的示例：
 * let callCount = 0;
 * const memoizedFn = memoize(function (a, b) {
 *   callCount += 1;
 *   return a + b;
 * })
 * memoizedFn(2, 3) // 5
 * memoizedFn(2, 3) // 5
 * console.log(callCount) // 1 
 */

失败的测试用例 #

let callCount = 0;
const memoizedFn = memoize(function (a, b) {
   callCount += 1;
   return a + b;
})
memoizedFn(122, 931)
memoizedFn(34, 216)
memoizedFn(22, 9)
memoizedFn(1, 803)
callCount // 预期为4，但我的代码返回3

问题分析与修复 #

错误根源 #

问题出在判断参数是否已缓存的逻辑上：你用arr.toString().match(args.toString())做检查，这是子串匹配而非精确匹配参数组合。

在测试用例的第三次调用memoizedFn(22,9)时，args.toString()是"22,9"，此时arr里已有[122,931]和[34,216]，arr.toString()的结果是"122,931,34,216"——这个字符串包含子串"22,9"（来自"122,931"中的"22,9"部分），所以match返回匹配结果，代码误判该参数已存在，跳过了fn的调用，导致callCount没有增加。而进入else分支遍历arr时，又找不到完全匹配的参数，函数最终没有返回正确值，但callCount少加了一次。

修复方案 #

方案1：使用Map缓存（推荐）

用Map存储参数与结果的映射，以参数的序列化字符串作为键，实现精确匹配：

function memoize(fn) {
    const cache = new Map();
    return function(...args) {
        const key = JSON.stringify(args);
        if (cache.has(key)) {
            return cache.get(key);
        }
        const result = fn(...args);
        cache.set(key, result);
        return result;
    }
}

方案2：改进数组存储的匹配逻辑

如果坚持用数组存储，需要逐个检查每个缓存参数的toString是否与当前参数完全相等，而非子串匹配：

function memoize(fn) {
    const argsList = [];
    const results = [];
    return function(...args) {
        const argStr = args.toString();
        // 精确查找是否存在完全匹配的参数
        const index = argsList.findIndex(item => item.toString() === argStr);
        if (index !== -1) {
            return results[index];
        }
        // 无匹配则执行函数并缓存
        const result = fn(...args);
        argsList.push(args);
        results.push(result);
        return result;
    }
}

为什么原逻辑会出错 #

arr.toString()会把所有缓存的参数数组拼接成一个大字符串，比如[[122,931], [34,216]]会变成"122,931,34,216"，此时任何参数组合的toString如果是这个大字符串的子串，都会被误判为已缓存。这种情况在参数包含连续数字时很容易发生，比如(22,9)的toString就会匹配(122,931)的toString的子串。

内容的提问来源于stack exchange，提问作者Manas Ghosh