JavaScript高频算法实战：从哈希表到深拷贝的避坑指南

1次阅读

共计 2895 个字符，预计需要花费 8 分钟才能阅读完成。

在实际的 JavaScript 开发中，我们经常会遇到一些经典的算法问题。这些问题虽然看似简单，但如果处理不当，很容易导致性能瓶颈或隐藏的 bug。今天我们就来聊聊几个高频出现的算法场景：两数之和、防抖函数、深拷贝以及数组扁平化与去重。这些场景看似基础，但在实际项目中往往能引发意想不到的问题。

两数之和是算法题中的经典问题，给定一个数组和一个目标值，找出数组中两个数之和等于目标值的索引。

最直观的解法是双重循环遍历数组，时间复杂度为 O(n²)。

function twoSum(nums: number[], target: number): number[] {for (let i = 0; i < nums.length; i++) {for (let j = i + 1; j < nums.length; j++) {if (nums[i] + nums[j] === target) {return [i, j];
            }
        }
    }
    return [];}

更优的解法是使用哈希表存储每个元素的差值，这样可以将时间复杂度降低到 O(n)。

function twoSum(nums: number[], target: number): number[] {const map = new Map<number, number>();
    for (let i = 0; i < nums.length; i++) {const complement = target - nums[i];
        if (map.has(complement)) {return [map.get(complement)!, i];
        }
        map.set(nums[i], i);
    }
    return [];}

防抖函数 (debounce) 用于控制函数调用频率，常见于输入框搜索、窗口 resize 等场景。

function debounce(fn: Function, delay: number) {
    let timer: number | null = null;
    return function() {if (timer) clearTimeout(timer);
        timer = setTimeout(() => {fn.apply(this, arguments);
        }, delay);
    };
}

function debounce(fn: Function, delay: number, immediate = false) {
    let timer: number | null = null;
    let debounced = function() {if (timer) clearTimeout(timer);
        if (immediate && !timer) {fn.apply(this, arguments);
        }
        timer = setTimeout(() => {if (!immediate) {fn.apply(this, arguments);
            }
            timer = null;
        }, delay);
    };

    debounced.cancel = function() {if (timer) {clearTimeout(timer);
            timer = null;
        }
    };

    return debounced;
}

JavaScript 中的深拷贝是一个常见需求，但直接使用 JSON.parse(JSON.stringify())有很多局限。

const obj = {date: new Date(),
    func: function() {},
    symbol: Symbol('test'),
    circular: null
};
obj.circular = obj;

// 会丢失函数、Symbol，遇到循环引用会报错
const cloned = JSON.parse(JSON.stringify(obj));

function deepClone(obj: any, hash = new WeakMap()): any {if (obj === null || typeof obj !== 'object') return obj;
    if (obj instanceof Date) return new Date(obj);
    if (obj instanceof RegExp) return new RegExp(obj);

    // 处理循环引用
    if (hash.has(obj)) return hash.get(obj);

    const cloneObj = new obj.constructor();
    hash.set(obj, cloneObj);

    // 处理 Symbol 属性
    const symKeys = Object.getOwnPropertySymbols(obj);
    for (const symKey of symKeys) {cloneObj[symKey] = deepClone(obj[symKey], hash);
    }

    // 处理普通属性
    for (const key in obj) {if (obj.hasOwnProperty(key)) {cloneObj[key] = deepClone(obj[key], hash);
        }
    }

    return cloneObj;
}

function flattenAndUnique(arr: any[]): any[] {return [].concat(...arr).filter((item, index, self) => self.indexOf(item) === index
    );
}

function flattenAndUnique(arr: any[]): any[] {const flat = (arr: any[]): any[] => 
        arr.reduce((acc, val) => 
            Array.isArray(val) ? acc.concat(flat(val)) : acc.concat(val), []);

    return [...new Set(flat(arr))];
}

使用 Benchmark.js 对上述算法进行性能测试发现：