如何判断真子集？

Question

在网上找到这样一个方法

function handleIncludes(childArr, fatherArr) {
  return childArr.every(v => fatherArr.includes(v));
}

let a = [1,2]
let b = [1,2,3]
let target = handleIncludes(a, b); // true

但是他有个问题，

let c = [2,2]
let target = handleIncludes(c, b); // true

这里应该false 应该brr没有两个2
希望有个高性能的简洁写法判断出真子集，大佬有写法吗？

Answer 1

可以试试，排序后转换成字符串比较。

let a = [1,2];
let b = [1,2,3];
function handleIncludes(childArr, fatherArr) {
  return fatherArr.sort().join().includes(childArr.sort().join());
}

Answer 2

无需排序，一次遍历，简单好理解的 O(n) 复杂度解法。

function handleIncludes(childArr, fatherArr) {
    const map = new Map();
    fatherArr.map(r => {
        if (map.get(r) === undefined) {
            map.set(r, 1);
        } else {
            map.set(r, map.get(r) + 1);
        }
    });
    for (let i = 0; i < childArr.length; i++) {
        const c = childArr[i];
        if( map.get(c) === undefined || map.get(c) === 0) return false;
        map.set(c, map.get(c) - 1);
    }
    return true;
}

Answer 3

暴力解法

function handleIncludes(childArr, fatherArr) {
    let cLen = childArr.length 
    if (cLen === 0) return false
    let i = 0
    while (i < cLen) {
      if (fatherArr.includes(childArr[i])) {
        let fIndex = fatherArr.findIndex(x => x === childArr[i])
        fatherArr.splice(fIndex, 1)
      } else {
        return false
      }
      i++
    }
    return true
}

Answer 4

是这样？

const f = (a, b) => {
    const bLen = b.length,aLen = a.length;    
    for (let bIndex = 0; bIndex < bLen && (bLen - bIndex >= aLen); bIndex++) {        
        let aIndex = 0;
        for (;aIndex < aLen; aIndex++) { if(b[bIndex + aIndex] !== a[aIndex]) break; }
        if(aIndex === aLen) return true;     
    }
    return false;
}

// f([4,1],[3,4,4,1,2])

Answer 5

不成熟的解决方案：

function handleIncludes(childArr, fatherArr) {
  const childSet = new Set()

  childArr.forEach(c => {
    let i = fatherArr.indexOf(c)
    if (~i && childSet.has(i)) i = fatherArr.indexOf(c, ++i)
    ~i && childSet.add(i)
  })

  return childSet.size === childArr.length
}

思路：

• 存入匹配项fatherArr数组下标
• 必要时跳过下标往后匹配
• 比较匹配的长度与childArr数组长度

Answer 6

比较两数组相同元素的个数即可

function count(arr) {
  return arr.reduce((c, k) => (c[k] = (c[k] ?? 0) + 1, c), {})
}

function handleIncludes(childArr, fatherArr) {
  const fCnts = count(fatherArr)
  const cCnts = count(childArr)
  return Object.keys(cCnts).every(k => cCnts[k] <= fCnts[k])
}

console.log(handleIncludes([1, 2], [1, 2, 3])) // true
console.log(handleIncludes([2, 2], [1, 2, 3])) // false
console.log(handleIncludes([3, 1], [1, 2, 3])) // true
console.log(handleIncludes([3, 4], [1, 2, 3])) // false
console.log(handleIncludes([0], [0, 0])) // true
console.log(handleIncludes([0, 0], [0, 0])) // true
console.log(handleIncludes([0, 0, 0], [0, 0])) // false

以上代码是线性复杂度，运行速度已经很快，需要进一步提升速度的话再往下看

如果 fatherArr 是固定不变的，那么 fCnts 也不变，可以提到外面，减少重复的计算
如果 childArr 很大，false 的几率更大的情况下，可以在计算 cCnts 的过程中提前退出，做法是每次加一就和 fCnts[k] 比较，更好的做法是改成初始为 fCnts[k]，每次减一和 0 比较，速度提升 \( 8\% \) 左右

const fCnts = [1, 2, 3].reduce((c, k) => (c[k] = (c[k] ?? 0) + 1, c), {})

function handleIncludes(childArr) {
  const c = {}
  return childArr.every(k => (c[k] = (c[k] ?? fCnts[k]) - 1) >= 0)
}

console.log(handleIncludes([1, 2])) // true
console.log(handleIncludes([2, 2])) // false
console.log(handleIncludes([3, 1])) // true
console.log(handleIncludes([3, 4])) // false