438. 找到字符串中所有字母异位词

/**
 * 给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的起始索引。
 *
 * @param {string} s 主字符串
 * @param {string} p 目标异位词
 * @returns {number[]} 包含所有异位词起始索引的数组
 */
 // 辅助函数：比较两个 Map 是否相等
    function mapsEqual(map1, map2) {
        if (map1.size !== map2.size) {
            return false;
        }
        for (const [key, value] of map1) {
            if (map2.get(key) !== value) {
                return false;
            }
        }
        return true;
    }

function findAnagrams(s, p) {
    const sLen = s.length;
    const pLen = p.length;

    // 检查边界条件，如果 s 的长度小于 p，则不可能存在异位词
    if (sLen < pLen) {
        return [];
    }

    // 使用 Map 作为哈希表，来存储字符的频率
    const pMap = new Map();
    const sMap = new Map();
    const result = [];

    // 初始化 pMap
    for (const char of p) {
        pMap.set(char, (pMap.get(char) || 0) + 1);
    }

    // 初始化第一个滑动窗口的 sMap
    for (let i = 0; i < pLen; i++) {
        const char = s[i];
        sMap.set(char, (sMap.get(char) || 0) + 1);
    }

    if (mapsEqual(sMap, pMap)) {
        result.push(0);
    }

    // 滑动窗口
    for (let i = pLen; i < sLen; i++) {
        // 右边界滑动：新进入窗口的字符
        const newChar = s[i];
        sMap.set(newChar, (sMap.get(newChar) || 0) + 1);

        // 左边界滑动：离开窗口的字符
        const oldChar = s[i - pLen];
        sMap.set(oldChar, sMap.get(oldChar) - 1);

        // 如果某个字符频率减为0，则从Map中删除，以保证比较的准确性
        if (sMap.get(oldChar) === 0) {
            sMap.delete(oldChar);
        }

        // 检查当前窗口是否为异位词
        if (mapsEqual(sMap, pMap)) {
            result.push(i - pLen + 1);
        }
    }

    return result;
}

在 JavaScript 中，直接使用 == 或 === 比较对象或数组通常是行不通的，因为它们比较的是内存地址，而不是内容。即使两个对象或数组看起来内容完全相同，只要它们不是同一个引用，比较结果就是 false。

如何比较数组是否相等？

比较数组是否相等和比较对象类似，但更简单一些，因为数组的键是数字索引。

长度相等：两个数组必须有相同的长度。
元素值相等：相同索引位置的元素值必须相等。

/**
 * 比较两个数组的内容是否相等
 * @param {Array} arr1
 * @param {Array} arr2
 * @returns {boolean}
 */
function arraysEqual(arr1, arr2) {
    // 检查是否为同一引用
    if (arr1 === arr2) {
        return true;
    }

    // 检查长度是否相等
    if (arr1.length !== arr2.length) {
        return false;
    }

    // 遍历元素并进行比较
    for (let i = 0; i < arr1.length; i++) {
        if (arr1[i] !== arr2[i]) {
            return false;
        }
    }

    return true;
}

如何比较对象是否相等？

要比较两个对象的内容是否相等，你需要遍历它们的属性，并确保以下条件都满足：

属性数量相等：两个对象必须有相同数量的自有（own）属性。
属性键名相等：两个对象必须有相同的属性键名。
属性值相等：相同键名对应的属性值必须相等。

以下是一个实现 objectsEqual 函数的例子

/**
 * 比较两个普通对象的内容是否相等
 * @param {object} obj1
 * @param {object} obj2
 * @returns {boolean}
 */
function objectsEqual(obj1, obj2) {
    // 检查是否为同一引用，这是最快的判断
    if (obj1 === obj2) {
        return true;
    }

    // 检查是否为对象且不为 null
    if (typeof obj1 !== 'object' || obj1 === null || typeof obj2 !== 'object' || obj2 === null) {
        return false;
    }

    const keys1 = Object.keys(obj1);
    const keys2 = Object.keys(obj2);

    // 检查属性数量是否相等
    if (keys1.length !== keys2.length) {
        return false;
    }

    // 遍历所有属性并进行比较
    for (const key of keys1) {
        // 如果属性值不相等，或者obj2中没有这个属性，则返回 false
        if (!obj2.hasOwnProperty(key) || obj1[key] !== obj2[key]) {
            return false;
        }
    }

    return true;
}

⚠️ 注意： 上述函数只适用于浅层比较，即如果对象属性的值是另一个对象，它无法进行深层比较。要处理这种情况，你需要使用递归。

438. 找到字符串中所有字母异位词

如何比较数组是否相等？

如何比较对象是否相等？

实现深层比较（Deep Equal）

全站热榜

创作者周榜