数组子集

说明

编写一个函数，接受两个参数，均为数组。数组中可以包含字符串和数字。如果第二个数组是第一个数组的子集，则返回 true。

换句话说，判断第二个数组中的每一项是否都在第一个数组中存在。

输入：包含数字和字符串的数组，包含数字和字符串的数组

输出：布尔值

示例

1arraySubset([2, 1, 3], [1, 2, 3]); // -> true
2arraySubset([2, 1, 1, 3], [1, 2, 3]); // -> true
3arraySubset([1, 2], [1, 2, 3]); // -> false
4arraySubset([1, 2, 3], [1, 2, 2, 3]); // -> false

提示

• 本题有多种解法，时间复杂度各不相同。
• 需要考虑重复元素的情况，例如某个元素在数组中出现两次。

---

1function arraySubset(arr, sub) {
2    // 你的代码在这里
3}

---

解法 1

1function arraySubset(arr, sub) {
2    if (sub.length > arr.length) {
3        return false;
4    }
5
6    for (let i = 0; i < sub.length; i++) {
7        const arrIndex = arr.indexOf(sub[i]);
8        if (arrIndex === -1) {
9            return false;
10        }
11
12        delete arr[arrIndex];
13    }
14
15    return true;
16}

工作原理

该函数首先进行一个简单的检查：根据定义，子集的大小不能超过超集。

接着遍历第二个数组中的每一项。函数在第一个数组中查找该项的索引。如果索引为 -1，表示该项不存在，立即返回 false。

否则，从第一个数组中删除该项。这确保了当该项在第二个数组中再次出现时，无法再使用第一个数组中的同一元素。

当成功遍历完第二个数组后，返回 true。

时间复杂度

我们有两个输入，分别用 m 和 n 表示其长度。

外层循环遍历 n 次，即 O(n)。循环内部调用了 indexOf()，而 indexOf() 本身是一个循环，引擎需要遍历数组来查找索引。

因此总的时间复杂度为：

O(m * n)

这是最终的时间复杂度。

空间复杂度

无论输入多大，使用的空间量保持不变，因此空间复杂度为：

O(1)

注意事项

• 该函数不是纯函数，因为它会修改第一个数组。为了避免这个问题，可以先对第一个数组进行复制，然后在副本上操作。这样虽然不会改变时间复杂度，但会使空间复杂度上升到 O(m)。解法 2 解决了这一问题。

---

解法 2

1function arraySubset(arr, sub) {
2    if (sub.length > arr.length) {
3        return false;
4    }
5
6    const arrCount = {};
7
8    for (let i = 0; i < arr.length; i++) {
9        const item = arr[i];
10        if (arrCount[item] !== undefined) {
11            arrCount[item]++;
12        } else {
13            arrCount[item] = 1;
14        }
15    }
16
17    for (let i = 0; i < sub.length; i++) {
18        const currentItem = sub[i];
19        if (arrCount[currentItem] === undefined) {
20            return false;
21        }
22
23        arrCount[currentItem]--;
24        if (arrCount[currentItem] === 0) {
25            delete arrCount[currentItem];
26        }
27    }
28
29    return true;
30}

工作原理

该解法通过计数的方式处理重复元素。首先遍历第一个数组，统计每个元素出现的次数，存储在一个对象中。然后遍历第二个数组，对于每个元素，检查其在计数对象中是否存在且数量大于零。若存在，则减少其计数；若计数归零，则从对象中移除该键。如果某个元素未找到或计数不足，则返回 false。全部检查通过后返回 true。

时间复杂度

此处所有对象操作的时间复杂度均为 O(1)，不影响整体计算。

首先遍历第一个数组，时间复杂度为 O(m)，循环内操作均为 O(1)。

接着遍历第二个数组，时间复杂度为 O(n)。由于该循环不在第一个循环内部，因此总时间为两者之和：

O(m + n)

相比 O(m * n) 有显著提升。

空间复杂度

本解法创建了一个与第一个数组元素数量相当的计数对象，因此空间复杂度为：

O(m)

---

扩展问题

当前解法适用于仅包含数字和字符串的数组。如果希望支持任意类型的数据，该如何处理？

对象类型的问题

使用普通对象无法解决此问题。因为对象的键只能是字符串，任何插入的对象都会被自动转换为字符串。这意味着不同的对象可能被转换成相同的键字符串，即使它们是不同引用。这会导致计数错误。

引入 Map

ES2015 引入了 Map 数据结构来解决此问题。Map 保留了键的原始类型，不会将键转换为字符串。

Map 支持键值对存储，同时具备类似集合的特性，如 has、set、get 和 delete 方法。它结合了对象和集合的优点。

将原代码中的对象替换为 Map 后，代码如下：

1function arraySubset(arr, sub) {
2    if (sub.length > arr.length) {
3        return false;
4    }
5
6    const arrMap = new Map();
7
8    for (let i = 0; i < arr.length; i++) {
9        const item = arr[i];
10        if (arrMap.has(item)) {
11            arrMap.set(item, arrMap.get(item) + 1);
12        } else {
13            arrMap.set(item, 1);
14        }
15    }
16
17    for (let i = 0; i < sub.length; i++) {
18        const currentItem = sub[i];
19        if (!arrMap.has(currentItem)) {
20            return false;
21        }
22
23        arrMap.set(currentItem, arrMap.get(currentItem) - 1);
24        if (arrMap.get(currentItem) === 0) {
25            arrMap.delete(currentItem);
26        }
27    }
28
29    return true;
30}

注意：最后两个测试用例返回 false 是正确的。虽然

1[{}, [], {}]

和

1[{}, [], {}]

在外观上相似，但它们的每一项都是独立的对象引用。第二个数组并不等于第一个数组。

关于引用与值的区别，可以复习一下对象类型与基本类型在存储方式上的差异，以获得更深入的理解。