给定一个数组，编写一个返回该数组所有可能的三元组/序列的函数？

Question

例如，给定A = [1, 2, 1, 1]，函数应该返回3。

仅创建三个不同的序列：(1, 2, 1), (1, 1, 1) and (2, 1, 1). 这个例子的正确答案是3。

• 给定A = [1, 2, 3, 4]，函数应该返回4。有四种方式：(1, 2, 3), (1, 2, 4), (1, 3, 4) and (2, 3, 4)。

• 给定A = [2, 2, 2, 2]，函数应该返回1。只有一种方法：(2, 2, 2).

• 给定A = [2, 2, 1, 2, 2]，函数应该返回4。有四种方式：(1, 2, 2), (2, 1, 2), (2, 2, 1) and (2, 2, 2)。

• 给定A = [1, 2]，函数应该返回0

为以下假设编写一个有效的算法：

N 是 [0..100,000] 范围内的整数；数组 A 的每个元素都是 [1..N] 范围内的整数。

下面是我的蛮力解决方案！

我想知道是否有人有更好更优化的解决方案？

检测到此解决方案的时间复杂度： O(N**3*log(N)) or O(N**4)

Answer 1

const theatreTickets = (array) => {&nbsp; let combos = []&nbsp; if(array.length < 2) {&nbsp; &nbsp; combos.length = 0&nbsp; }&nbsp; for(let i = 0; i <= array.length; i++) {&nbsp; &nbsp; for(let j = i + 1; j <= array.length - 1; j++) {&nbsp; &nbsp; &nbsp; for(let k = j + 1; k <= array.length - 1; k++) {&nbsp; &nbsp; &nbsp; &nbsp; combos.push([array[i], array[j], array[k]])&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; }&nbsp; combos = Array.from(new Set(combos.map(JSON.stringify)), JSON.parse)&nbsp; return combos.length}console.log(theatreTickets([1, 2, 1, 1])) // Should Be 3

Answer 2

我认为你需要组合，组合和独特的算法。它会起作用的。示例如下。function combine(items, numSubItems) {&nbsp; &nbsp; &nbsp; &nbsp; var result = [];&nbsp; &nbsp; &nbsp; &nbsp; var indexes = new Array(numSubItems);&nbsp; &nbsp; &nbsp; &nbsp; for (var i = 0 ; i < numSubItems; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; indexes[i] = i;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; while (indexes[0] < (items.length - numSubItems + 1)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; var v = [];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (var i = 0 ; i < numSubItems; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; v.push(items[indexes[i]]);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result.push(v);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; indexes[numSubItems - 1]++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; var l = numSubItems - 1; // reference always is the last position at beginning&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while ( (indexes[numSubItems - 1] >= items.length) && (indexes[0] < items.length - numSubItems + 1)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; l--; // the last position is reached&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; indexes[l]++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (var i = l +1 ; i < numSubItems; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; indexes[i] = indexes[l] + (i - l);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return result;&nbsp; &nbsp; }&nbsp; &nbsp; var combinations = combine([1,2,1,1], 3);&nbsp; &nbsp; console.log([...new Set(combinations.map(x => x.join(",")))]);&nbsp; &nbsp; combinations = combine([1,2,3,4], 3);&nbsp; &nbsp; console.log([...new Set(combinations.map(x => x.join(",")))]);