Javascript数组包含/包含子数组

Question

我需要检查一个数组是否包含另一个数组.子阵列的顺序很重要,但实际的偏移并不重要.它看起来像这样:

var master = [12, 44, 22, 66, 222, 777, 22, 22, 22, 6, 77, 3]; 

var sub = [777, 22, 22]; 

所以我想知道是否master 包含以下内容sub:

if(master.arrayContains(sub) > -1){
    //Do awesome stuff
}

那怎样才能以优雅/高效的方式完成呢？

Answer 1

从fromIndex参数的一点帮助

该解决方案在索引上具有闭包,用于在数组中搜索元素的开始位置.如果找到子数组的元素,则搜索下一个元素将以递增的索引开始.

function hasSubArray(master, sub) {
    return sub.every((i => v => i = master.indexOf(v, i) + 1)(0));
}

var array = [12, 44, 22, 66, 222, 777, 22, 22, 22, 6, 77, 3];

console.log(hasSubArray(array, [777, 22, 22]));
console.log(hasSubArray(array, [777, 22, 3]));
console.log(hasSubArray(array, [777, 777, 777]));
console.log(hasSubArray(array, [42]));

Answer 2

var master = [12, 44, 22, 66, 222, 777, 22, 22, 22, 6, 77, 3]; 

var sub = [777, 22, 22]; 

console.log(master.join(',').includes(sub.join(',')))

//true

您可以console.log(master.join(',').includes(sub.join(',')))使用 include 方法通过简单的这行代码来完成此操作

Answer 3

令人惊讶的是，这种错误实现的频率如此之高。

\n

我们\xe2\x80\x99要寻找的是数学意义上的子串。

\n

\n

在数学中，序列是对象的枚举集合，其中允许重复且顺序很重要。

\n

\n

\n

在数学中，给定序列的子序列是可以通过删除一些元素或不删除元素而从给定序列导出的序列，而不改变剩余元素的顺序。

\n

\n

\n

由原始序列中的连续元素组成的子序列，例如 \xe2\x9f\xa8 B, C, D \xe2\x9f\xa9 来自 \xe2\x9f\xa8 A, B, C, D, E , F \xe2\x9f\xa9 是一个子串。

\n

\n

请注意，此处的 \xe2\x80\x9cstring\xe2\x80\x9d 可以包含任何元素，并且不限于 Unicode 代码点序列。

\n

实际上，之前的所有答案都存在许多可能的缺陷之一：

\n

\n
• array1.toString().includes(array2.toString())当数组元素包含逗号时，字符串连接方法 ( ) 会失败。（例如：[ "a", "b" ]不包含[ "a,b" ]。
\n
• 一些实现检查超出数组范围。（示例：[ "3" ]不包含[ "3", undefined ]，只是因为两者都有报告array[1]） 。undefined
\n
• 某些实现无法正确处理重复。
\n
• 某些实现不是\xe2\x80\x99 正确检查子字符串（在数学意义上），而是检查子集或子序列或其他内容。
\n
• 某些实现不考虑空数组。空字符串是每个字符串的子字符串。
\n

\n

检查一个数组是否构成另一个数组的 \xe2\x80\x9csubstring\xe2\x80\x9d

\n

立即，这可以正确处理空数组。

\n

然后，它通过与潜在子数组的第一个元素匹配来构建候选起始索引列表。

\n

找到切片的每个元素与完整数组的索引逐个匹配的第一个候选者，以候选者起始索引为偏移量。\n检查的索引也必须存在于完整数组中，因此Object.hasOwn。

\n

\r\n

\r\n

const isSubArray = (full, slice) => {\n    if(slice.length === 0){\n      return true;\n    }\n\n    const candidateIndexes = full\n        .map((element, fullIndex) => ({\n          matched: element === slice[0],\n          fullIndex\n        }))\n        .filter(({ matched }) => matched),\n      found = candidateIndexes\n        .find(({ fullIndex }) => slice.every((element, sliceIndex) => Object.hasOwn(full, fullIndex + sliceIndex) && element === full[fullIndex + sliceIndex]));\n\n    return Boolean(found);\n  };\n\nconsole.log(isSubArray([], []) === true);\nconsole.log(isSubArray([ 0 ], []) === true);\nconsole.log(isSubArray([ 0, 1, 2 ], [ 1, 2 ]) === true);\nconsole.log(isSubArray([ 0, 1, 1, 2 ], [ 0, 1, 2 ]) === false);\nconsole.log(isSubArray([ 2, 1 ], [ 1, 2 ]) === false);\nconsole.log(isSubArray([ 1, 2, 3 ], [ 2, 3, undefined ]) === false);\nconsole.log(isSubArray([ 0, 1, 1, 2, 3 ], [ 1, 1, 2 ]) === true);\nconsole.log(isSubArray([ 0, 1, 1, 2, 3 ], [ 1, 2 ]) === true);\nconsole.log(isSubArray([ 0, 1, 1, 2, 3 ], [ 0, 1, 1, 1 ]) === false);\nconsole.log(isSubArray([ "a", "b" ], [ "a,b" ]) === false);

\r\n

.as-console-wrapper { max-height: 100% !important; top: 0; }

\r\n

\r\n

\r\n

\n

是的，这具有二次复杂度。\n使用Trees或Ropes可能有更有效的实现。\n您可能还想研究一些有效的子字符串搜索算法并尝试将它们应用于此问题。

\n

获取找到的\xe2\x80\x9csubstring\xe2\x80\x9d的索引，或者-1没有找到

\n

它\xe2\x80\x99s 基本上是相同的代码，但return true;替换为return 0;, 并return Boolean(found);替换为return found?.fullIndex ?? -1;.

\n

\r\n

\r\n

const findSubArrayIndex = (full, slice) => {\n    if(slice.length === 0){\n      return 0;\n    }\n\n    const candidateIndexes = full\n        .map((element, fullIndex) => ({\n          matched: element === slice[0],\n          fullIndex\n        }))\n        .filter(({ matched }) => matched),\n      found = candidateIndexes\n        .find(({ fullIndex }) => slice.every((element, sliceIndex) => Object.hasOwn(full, fullIndex + sliceIndex) && element === full[fullIndex + sliceIndex]));\n\n    return found?.fullIndex ?? -1;\n  };\n\nconsole.log(findSubArrayIndex([], []) === 0);\nconsole.log(findSubArrayIndex([ 0 ], []) === 0);\nconsole.log(findSubArrayIndex([ 0, 1, 2 ], [ 1, 2 ]) === 1);\nconsole.log(findSubArrayIndex([ 0, 1, 1, 2 ], [ 0, 1, 2 ]) === -1);\nconsole.log(findSubArrayIndex([ 2, 1 ], [ 1, 2 ]) === -1);\nconsole.log(findSubArrayIndex([ 1, 2, 3 ], [ 2, 3, undefined ]) === -1);\nconsole.log(findSubArrayIndex([ 0, 1, 1, 2, 3 ], [ 1, 1, 2 ]) === 1);\nconsole.log(findSubArrayIndex([ 0, 1, 1, 2, 3 ], [ 1, 2 ]) === 2);\nconsole.log(findSubArrayIndex([ 0, 1, 1, 2, 3 ], [ 0, 1, 1, 1 ]) === -1);\nconsole.log(findSubArrayIndex([ "a", "b" ], [ "a,b" ]) === -1);

\r\n

.as-console-wrapper { max-height: 100% !important; top: 0; }

\r\n

\r\n

\r\n

\n

半可接受的替代方案：JSON

\n

对两个数组进行 JSON 编码也可能是一种可行的策略。\n这里，需要删除潜在子数组周围的[\xe2\x80\xa6 ，然后会告诉您该 JSON 字符串是否包含在另一个 JSON 字符串中。 \n这与简单的字符串连接相反，\xe2\x80\x8a\xe2\x80\x94\xe2\x80\x8a]includesjoin方法\xe2\x80\x8a\xe2\x80\x94\xe2\x80\x8a，因为 JSON 有分隔符不能逐字出现在编码元素中；如果它们确实出现在原始元素中，则它们\xe2\x80\x99d 会被正确转义。

\n

需要注意的是，这对于不可在 JSON 中编码的值不起作用。

\n

\r\n

\r\n

const isSubArray = (full, slice) => JSON.stringify(full)\n    .includes(JSON.stringify(slice).replaceAll(/^\\[|\\]$/g, ""));\n\nconsole.log(isSubArray([], []) === true);\nconsole.log(isSubArray([ 0 ], []) === true);\nconsole.log(isSubArray([ 0, 1, 2 ], [ 1, 2 ]) === true);\nconsole.log(isSubArray([ 0, 1, 1, 2 ], [ 0, 1, 2 ]) === false);\nconsole.log(isSubArray([ 2, 1 ], [ 1, 2 ]) === false);\nconsole.log(isSubArray([ 1, 2, 3 ], [ 2, 3, undefined ]) === false);\nconsole.log(isSubArray([ 0, 1, 1, 2, 3 ], [ 1, 1, 2 ]) === true);\nconsole.log(isSubArray([ 0, 1, 1, 2, 3 ], [ 1, 2 ]) === true);\nconsole.log(isSubArray([ 0, 1, 1, 2, 3 ], [ 0, 1, 1, 1 ]) === false);\nconsole.log(isSubArray([ "a", "b" ], [ "a,b" ]) === false);

\r\n

.as-console-wrapper { max-height: 100% !important; top: 0; }

\r\n

\r\n

\r\n

\n

Answer 4

编辑

最初误解了问题。

function arrayContainsSub(arr, sub) {
        var first = sub[0],
            i = 0,
            starts = [];

        while (arr.indexOf(first, i) >= 0) {
            starts.push(arr.indexOf(first, i));
            i = arr.indexOf(first, i) + 1;
        }

        return !!starts
                    .map(function(start) {
                        for (var i = start, j = 0; j < sub.length; i++, j++) {
                            if (arr[i] !== sub[j]) {
                                return false;
                            }
                            if (j === sub.length - 1 && arr[i] === sub[j]) {
                                return true;
                            }
                        };

                    }).filter(function(res) {
                        return res;
                    }).length;
    }

该解决方案将递归地检查所有可用的起始点，即子项的第一个索引在数组中具有匹配项的点

保留旧答案，以防对搜索者有用。

if(master.indexOf(sub) > -1){ //Do awesome stuff }

重要的是要记住，这只会匹配master字面引用sub。如果它只包含一个具有相同内容的数组，但引用了不同的特定对象，则它将不匹配。