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
}

那么如何以优雅/高效的方式完成这个任务呢？

- Victor Axelsson

---

在以优雅的方式实现之前，先以某种方式进行实现。有什么想法吗？ - zerkms

在JS中，对于你的问题没有优雅的解决方式。你最好看看JS库，比如Underscore。 - hindmost

你必须看看库——这太悲观了，真的。 - zerkms

你想在主数组中正确地按顺序找到777...22...222，对吗？ - Nina Scholz

@NinaScholz 是的，顺序很重要。 - Victor Axelsson

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]));

- Nina Scholz

---

sub=[777, 22, 3] 返回 true。这是有意为之的吗？虽然 OP 说“实际偏移量并不重要”，但我不太确定这是什么意思。 - mpen

我在问您的代码是否是有意匹配这样，因为仅凭您的示例，我本来会认为 [777,22,22] 必须在主数组中是连续的，但事实并非如此。 - mpen

实际上，您还有另一个问题。应该使用index = i + 1来防止在相同字符上进行双重匹配。否则，[777, 777, 777]也会匹配！ - mpen

@mpen，ad1（[777, 22, 3]）：是的，这是有意为之的，因为22的索引比777大，而3的索引比22大。 ad2（[777, 22, 22]）：是的，没错。 ad3（[777, 777, 777]）：你说得对，找到的索引必须增加。 - Nina Scholz

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

您可以通过使用include方法，简单地编写以下代码：console.log(master.join(',').includes(sub.join(',')))来实现此操作。

- Mohmadhaidar devjiyani

---

如果对您而言顺序不重要的话，您应该首先对数组进行排序：var master = [12, 44, 22, 66, 222, 777, 22, 22, 22, 6, 77, 3];var sub = [777, 22, 22];console.log(master.sort().join(',').includes(sub.sort().join(','))) - rebinnaf

Answer 3

令人惊讶的是，这种实现经常不正确。

我们要找的是数学意义上的子字符串。

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

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

由原始序列中连续运行的元素组成的子序列，例如从 ⟨ A，B，C，D，E，F ⟩ 中的 ⟨ B，C，D ⟩，是一个子字符串。

请注意，“字符串”在此处可以包含任何元素，并不限于Unicode代码点序列。

实际上，所有先前的答案都有许多可能的缺陷：

• 使用字符串拼接方法(array1.toString().includes(array2.toString()))时，如果数组元素中有逗号，则会失败。(例如：[ "a", "b" ]不包含[ "a,b" ] )。
• 一些实现在数组边界之外进行检查。(例如：[ "3" ]不包含[ "3", undefined ], 只是因为array[1]对于两者都报告undefined)。
• 一些实现不能正确处理重复。
• 一些实现不能正确地检查子字符串(在数学意义上)，而是检查子集或子序列等其他内容。
• 一些实现没有考虑空数组。空字符串是每个字符串的子串。

检查一个数组是否构成另一个数组的“子串”

首先，这个方法可以正确处理空数组。

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

查找第一个候选项，其中切片中的每个元素与完整数组从候选项起始索引偏移量相匹配。

所检查的索引也必须存在于完整数组中，因此需要使用Object.hasOwn函数。

const isSubArray = (full, slice) => {
    if(slice.length === 0){
      return true;
    }

    const candidateIndexes = full
        .map((element, fullIndex) => ({
          matched: element === slice[0],
          fullIndex
        }))
        .filter(({ matched }) => matched),
      found = candidateIndexes
        .find(({ fullIndex }) => slice.every((element, sliceIndex) => Object.hasOwn(full, fullIndex + sliceIndex) && element === full[fullIndex + sliceIndex]));

    return Boolean(found);
  };

console.log(isSubArray([], []) === true);
console.log(isSubArray([ 0 ], []) === true);
console.log(isSubArray([ 0, 1, 2 ], [ 1, 2 ]) === true);
console.log(isSubArray([ 0, 1, 1, 2 ], [ 0, 1, 2 ]) === false);
console.log(isSubArray([ 2, 1 ], [ 1, 2 ]) === false);
console.log(isSubArray([ 1, 2, 3 ], [ 2, 3, undefined ]) === false);
console.log(isSubArray([ 0, 1, 1, 2, 3 ], [ 1, 1, 2 ]) === true);
console.log(isSubArray([ 0, 1, 1, 2, 3 ], [ 1, 2 ]) === true);
console.log(isSubArray([ 0, 1, 1, 2, 3 ], [ 0, 1, 1, 1 ]) === false);
console.log(isSubArray([ "a", "b" ], [ "a,b" ]) === false);

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

这具有二次复杂度。

可能有更有效的实现方法，可以使用树或Ropes。

您也可以研究一些高效的子字符串搜索算法并尝试将它们应用于此问题。

获取找到的“子字符串”的索引，如果未找到则为-1

基本上是相同的代码，但将return true;替换为return 0;，将return Boolean(found);替换为return found?.fullIndex ?? -1;。

const findSubArrayIndex = (full, slice) => {
    if(slice.length === 0){
      return 0;
    }

    const candidateIndexes = full
        .map((element, fullIndex) => ({
          matched: element === slice[0],
          fullIndex
        }))
        .filter(({ matched }) => matched),
      found = candidateIndexes
        .find(({ fullIndex }) => slice.every((element, sliceIndex) => Object.hasOwn(full, fullIndex + sliceIndex) && element === full[fullIndex + sliceIndex]));

    return found?.fullIndex ?? -1;
  };

console.log(findSubArrayIndex([], []) === 0);
console.log(findSubArrayIndex([ 0 ], []) === 0);
console.log(findSubArrayIndex([ 0, 1, 2 ], [ 1, 2 ]) === 1);
console.log(findSubArrayIndex([ 0, 1, 1, 2 ], [ 0, 1, 2 ]) === -1);
console.log(findSubArrayIndex([ 2, 1 ], [ 1, 2 ]) === -1);
console.log(findSubArrayIndex([ 1, 2, 3 ], [ 2, 3, undefined ]) === -1);
console.log(findSubArrayIndex([ 0, 1, 1, 2, 3 ], [ 1, 1, 2 ]) === 1);
console.log(findSubArrayIndex([ 0, 1, 1, 2, 3 ], [ 1, 2 ]) === 2);
console.log(findSubArrayIndex([ 0, 1, 1, 2, 3 ], [ 0, 1, 1, 1 ]) === -1);
console.log(findSubArrayIndex([ "a", "b" ], [ "a,b" ]) === -1);

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

次佳方案：JSON

将两个数组都进行JSON编码也是可行的策略。在这里，潜在子数组周围的[…]需要被移除，然后使用includes函数来判断一个JSON字符串是否包含在另一个JSON字符串中。这种方法可以成功实现——与简单的字符串拼接或join方式相比之下——因为JSON具有分隔符，这些分隔符不能出现在编码的元素中。如果它们在原始元素中出现，它们会被正确地转义。

但需要注意的是，对于无法进行JSON编码的值，此方法将不起作用。

const isSubArray = (full, slice) => JSON.stringify(full)
    .includes(JSON.stringify(slice).replaceAll(/^\[|\]$/g, ""));

console.log(isSubArray([], []) === true);
console.log(isSubArray([ 0 ], []) === true);
console.log(isSubArray([ 0, 1, 2 ], [ 1, 2 ]) === true);
console.log(isSubArray([ 0, 1, 1, 2 ], [ 0, 1, 2 ]) === false);
console.log(isSubArray([ 2, 1 ], [ 1, 2 ]) === false);
console.log(isSubArray([ 1, 2, 3 ], [ 2, 3, undefined ]) === false);
console.log(isSubArray([ 0, 1, 1, 2, 3 ], [ 1, 1, 2 ]) === true);
console.log(isSubArray([ 0, 1, 1, 2, 3 ], [ 1, 2 ]) === true);
console.log(isSubArray([ 0, 1, 1, 2, 3 ], [ 0, 1, 1, 1 ]) === false);
console.log(isSubArray([ "a", "b" ], [ "a,b" ]) === false);

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

- Sebastian Simon

Answer 4

我有一个快速的想法，但效率取决于数组的大小。

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

if ((master.toString()).indexOf(sub.toString()) > -1 ){
    //body here
}

- Mahesh Talada

---

这实际上是我在我的实现中采用的解决方案，我喜欢它因为它很容易理解。但是我觉得它并没有真正解决问题，因为有两个原因：它可以在数组上使用原型，并且我应该获取数组中的实际索引（而不是字符串）。谢谢！ - Victor Axelsson

如果 var master = [12, 44, 22, 66, 222, 777, 22, 224, 22, 6, 77, 3]; var sub = [777, 22, 22];，那将非常危险。 - deblocker

@deblocker，可能是这样的someArray.map(value => value.toString()).join(";")，这样字符串会被分隔，避免误匹配。 - heltonbiker

Answer 5

最简单的匹配子集/子数组的方法

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

const sub1 = [777, 44, 222]; 
const sub2 = [777, 18, 66]; 

sub1.every(el => master.includes(el));  // reture true
sub2.every(el => master.includes(el));  // return false

- Manoj Rana

---

“子数组的顺序很重要” - 你完全忽略了顺序。 - Sebastian Simon

Answer 6

如果顺序很重要，那么它必须是一个实际的子数组（而不是数组的子集），如果值严格为整数，则尝试使用此方法。

console.log ( master.join(",").indexOf( subarray.join( "," ) ) == -1 )

如需仅检查值，请查看fiddle（不使用第三方库）。

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

var sub = [777, 22, 22]; 

function isSubset( arr1, arr2 )
{
    for (var i=0; i<arr2.length; i++)
    {
        if ( arr1.indexOf( arr2[i] ) == -1 )
        {
          return false;
        }
    }
    return true;
}
console.log( isSubset( master, sub ) );

这里也有更快的选项解释。

- gurvinder372

---

@zerkms 为什么这么说？它是可以工作的。它输出了“true”。 - gurvinder372

对于我的例子来说，它应该返回“false”。 - zerkms

@zerkms明白了，我理解您的意思。我正在尝试编写一个可以处理相同值的多个实例的程序。 - gurvinder372

这没有考虑到子数组中的重复。 - Sebastian Simon

Answer 7

编辑

最初误解了问题。

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){ //做一些很棒的事情 }

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

- Mild Fuzz

---

arrayContainsSub([], []) 和 arrayContainsSub([ 3 ], []) 应该是 true。arrayContainsSub([ 3, 4, 4 ], [ 4, 4, undefined ]) 应该是 false。 - Sebastian Simon

Answer 8

你可以尝试使用filter和indexOf来实现，代码如下：

注意：此代码适用于子数组中不考虑顺序的情况。

Array.prototype.arrayContains = function (sub) {
  var self = this;
  var result = sub.filter(function(item) {
    return self.indexOf(item) > -1;
  });
  return sub.length === result.length;
}

示例 这里。

更新：返回主数组中子数组的索引（覆盖子数组中的顺序）

Array.prototype.arrayContains = function(sub) {
  var first;
  var prev;
  for (var i = 0; i < sub.length; i++) {
    var current = this.indexOf(sub[i]);
    if (current > -1) {
      if (i === 0) {
        first = prev = current;
        continue;
      } else {
        if (++prev === current) {
          continue;
        } else {
          return -1;
        }
      }
    } else {
      return -1;
    }
  }
  return first;
}

演示：这里

- Nguyen Tran

---

我喜欢你使用了原型，并且它很简单。如果您可以使其返回数组indexOf，则我将愿意接受它作为答案。 - Victor Axelsson

这对于空子数组不返回任何内容。[1, 2, 2].arrayContains([2, 2]) 应该是 true。 - Sebastian Simon

Answer 9

对于这个答案，我保留子数组的顺序。这意味着，子数组的元素应该是连续的。如果与主数组相比有任何额外的元素，则返回false。

我分3步完成：

1. 在master中找到sub的第一个元素的索引，并将其存储在数组matched_index []中。
2. 对于matched_index []中的每个条目，请检查从s_index开始，sub的每个元素是否与master相同。如果不匹配，则返回false并中断子循环的for循环，开始下一个matched_index []中的元素的for循环。
3. 在任何时候，如果在master中找到相同的sub数组，则循环将中断并返回true。

function hasSubArray(master,sub){

    //collect all master indexes matching first element of sub-array
    let matched_index = [] 
    let start_index = master.indexOf(master.find(e=>e==sub[0]))
    
    while(master.indexOf(sub[0], start_index)>0){
        matched_index.push(start_index)
        let index = master.indexOf(sub[0], start_index)
        start_index = index+1
    } 

    let has_array //flag
    
    for(let [i,s_index] of matched_index.entries()){
        for(let [j,element] of sub.entries()){
            if(element != master[j+s_index]) {
                has_array = false
                break
            }else has_array = true
        }
        if (has_array) break
    }
    return has_array
}

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

console.log(hasSubArray(master, [777, 22, 22]));
console.log(hasSubArray(master, [777, 22, 3]));
console.log(hasSubArray(master, [777, 777, 777]));
console.log(hasSubArray(master, [44]));
console.log(hasSubArray(master, [22, 66]));

- Jaimin Patel

---

hasSubArray(master, []) 应该为 true; hasSubArray(master, [ 3, undefined ]) 应该为 false。 - Sebastian Simon

Answer 10

  async function findSelector(a: Uint8Array, selector: number[]): Promise<number> {
    let i = 0;
    let j = 0;
    while (i < a.length) {
      if (a[i] === selector[j]) {
        j++;
        if (j === selector.length) {
          return i - j + 1;
        }
      } else {
        j = 0;
      }
      i++;
    }
    return -1;
  }

- John Targaryen

---

为什么这是一个异步函数？findSelector([], [])和findSelector([2], [])应该是true。 - Sebastian Simon