一种选项是对这两个数组进行排序，然后同时遍历比较元素。如果一个子集合候选元素在超集合中找不到，那么前者不是子集合。排序通常是O(n*log(n))的，比较是O(max(s,t))的，其中s和t是数组大小，总时间复杂度为O(m*log(m))，其中m=max(s,t)。
function superbag(sup, sub) {
sup.sort();
sub.sort();
var i, j;
for (i=0,j=0; i<sup.length && j<sub.length;) {
if (sup[i] < sub[j]) {
++i;
} else if (sup[i] == sub[j]) {
++i; ++j;
} else {
return false;
}
}
return j == sub.length;
}
如果实际代码中的元素是整数，则可以使用特定的整数排序算法（例如
基数排序）来实现O(max(s,t))的时间复杂度，但如果包很小，则内置的
Array.sort可能比自定义整数排序更快。
具有潜在较小时间复杂度的解决方案是创建一个包类型。整数包特别容易。翻转包的现有数组：创建一个对象或一个数组，将整数作为键，重复计数作为值。使用数组不会浪费空间，因为
Javascript中的数组是稀疏的。您可以使用包操作进行子包或超包检查。例如，从子候选项中减去超级候选项并测试结果是否非空。或者，
contains操作应该是O(1)（或可能是O(log(n))），因此循环遍历子包候选项并测试超级包含是否超过每个子包元素的子包包含应该是O(n)或O(n*log(n))。
以下内容未经测试。实现
isInt留作练习。
function IntBag(from) {
if (from instanceof IntBag) {
return from.clone();
} else if (from instanceof Array) {
for (var i=0; i < from.length) {
this.add(from[i]);
}
} else if (from) {
for (p in from) {
if (isInt(p) && isInt(from[p])) {
this.add(p, from[p]);
}
}
}
}
IntBag.prototype=[];
IntBag.prototype.size=0;
IntBag.prototype.clone = function() {
var clone = new IntBag();
this.each(function(i, count) {
clone.add(i, count);
});
return clone;
};
IntBag.prototype.contains = function(i) {
if (i in this) {
return this[i];
}
return 0;
};
IntBag.prototype.add = function(i, count) {
if (!count) {
count = 1;
}
if (i in this) {
this[i] += count;
} else {
this[i] = count;
}
this.size += count;
};
IntBag.prototype.remove = function(i, count) {
if (! i in this) {
return;
}
if (!count) {
count = 1;
}
this[i] -= count;
if (this[i] > 0) {
this.size -= count;
} else {
this.size -= count + this[i];
delete this[i];
}
};
IntBag.prototype.each = function(f) {
var i;
foreach (i in this) {
f(i, this[i]);
}
};
IntBag.prototype.find = function(p) {
var result = [];
var i;
foreach (i in this.elements) {
if (p(i, this[i])) {
return i;
}
}
return null;
};
IntBag.prototype.sub = function(other) {
other.each(function(i, count) {
this.remove(i, count);
});
return this;
};
IntBag.prototype.union = function(other) {
var union = this.clone();
other.each(function(i, count) {
if (union.contains(i) < count) {
union.add(i, count - union.contains(i));
}
});
return union;
};
IntBag.prototype.intersect = function(other) {
var intersection = new IntBag();
this.each(function (i, count) {
if (other.contains(i)) {
intersection.add(i, Math.min(count, other.contains(i)));
}
});
return intersection;
};
IntBag.prototype.diff = function(other) {
var mine = this.clone();
mine.sub(other);
var others = other.clone();
others.sub(this);
mine.union(others);
return mine;
};
IntBag.prototype.subbag = function(super) {
return this.size <= super.size
&& null !== this.find(
function (i, count) {
return super.contains(i) < this.contains(i);
}));
};
如果您想禁止元素的重复出现，可以参考 "比较JavaScript数组" 中的示例实现一个对象集合。
