JS和查找表问题

前言

查找，一直是算法问题中一个经典的部分，而JS也经常有在一个数组、字符串、对象等中进行查找的需求

始祖：二分查找

这个我在另一篇文章里有提到。JS和双索引查找

Set数据结构在查找中的应用

ES6之前是不支持Set这种数据结构的，有些适合Set的场景也只能用数组代替，然后再去重，所以前端面试对于数组去重的考察也是很多的。
这里我们以leetcode的349题为例：我们需要把第二个数组的元素插入到第一个数组里，相同才保留，并且保证最后的数组是没有重复元素的。
常规的思路需要去几次重:

var intersection = function (nums1, nums2) {
    nums1 = nums1.filter((e, i) => { return nums1.indexOf(e) === i })
    var result = [];
    nums2.forEach(e => {
        if (nums1.indexOf(e) !== -1) {
            result.push(e);
        }
    })
    return result.filter((e, i) => { return result.indexOf(e) === i });
};

但是我们有了Set这种数据结构就方便多了：

var intersection = function (nums1, nums2) {
    let set1 = new Set(nums1);
    let result = new Set();
    nums2.forEach(e => {
        if (set1.has(e)) {
            result.add(e);
        }
    })
    return Array.from(result);
};

Map数据结构在查找中的应用

某些场景下，我们需要对数组中的元素做一些记录，比如使用哈希表，JS中之前实现哈希表都是用对象模拟，有了Map数据结构，在这些场景下我们就可以使用它来解决这些问题了。
这里我们以leetcode的349题为例：我们需要把第二个数组的元素插入到第一个数组里，相同就保留，不要求去重。
没有Map数据结构的写法：

var intersect = function (nums1, nums2) {
    let record = {};
    nums1.forEach((e) => {
        record[e] > 0 ? record[e]++ : record[e] = 1;
    });
    let result = [];
    nums2.forEach(e => {
        if (record[e] > 0) {
            result.push(e);
            //哈希表中对应值减一
            record[e]--;
        }
    });
    return result;
};

Map写法：

var intersect = function (nums1, nums2) {
    let record = new Map();
    nums1.forEach((e) => {
        record.has(e) ? record.set(e, (record.get(e) + 1)) : record.set(e, 1);
    });
    let result = [];
    nums2.forEach(e => {
        if (record.has(e) && record.get(e) > 0) {
            result.push(e);
            record.set(e, (record.get(e) - 1));
            if(record.get(e)==0){
                record.delete(e);
            }
        }
    });
    return result;
};

综合查找

很多时候，Map和Set都是作为一种辅助数据结构帮助解决问题的，所以根据要场景结合多种算法来达成目标。
比如leetcode的219题：判断在一个i~j(长度为k)的滑动窗口内是否有两个相等的数字
我们使用一个Set作为辅助数据结构，存储这个滑动窗口的元素，为了保证长度为k，当滑动窗口移动的时候，就删除一个元素

var containsNearbyDuplicate = function (nums, k) {
    let record = new Set()
    for (let i = 0; i < nums.length; i++) {
        let e = nums[i];
        if (record.has(e)) return true
        record.add(e)
        if (record.size === k + 1) record.delete(nums[i - k])
    }
    return false
};

总结

Map和Set在实际业务场景中还有很多可以应用的地方，不管是做算法还是处理前端的一些对象、数组数据。