对于每个元素，计算有多少给定的子数组包含它

Question

当我在一次编码竞赛中解决一个问题时，我发现我需要这样做：给定表示子数组索引的对（i，j）;对于每个元素，计算包含它的子数组的数量。例如：

我们有一个数组＜code＞[7，-2，-7，0，6]，对是＜code＜（0，2）、（1，4）、（2，3）、（0，3）＜/code>，那么结果数组将是＜code>[2，3，4，3，1]，因为第一个元素在子数组＜code>（0，2），＜/code＞（0，3）中，第二个元素在＜code〈0，2》，（1，4），＜/code>。

当然，一种方法是手动计数，使用数组和计数，但这可能会给我TLE，因为数组大小和对数太大而无法做到这一点。我还在其他地方读到，您可以使用一个额外的数组在其中存储“东西”（为每个子数组添加/减去一些东西），然后遍历该数组以找出答案，但我不记得我在哪里读到过它。

如果您对我的算法也有任何改进，这里是原始问题：

给定大小为n的数组

我知道一种方法来查找子数组，其总和等于0：https://www.geeksforgeeks.org/print-all-subarrays-with-0-sum/。但是我上面已经说过的第二个任务，我还没有弄清楚。如果您对此有一些想法，请告诉我并非常感谢您。

Answer 1

您可以取每对并在开始的地方标记1，在停止的地方标记-1（在单独的数组中）。这些表示与某个索引重叠的范围数量的变化。然后迭代该列表以收集这些变化并将其累积为绝对数字（重叠范围的数量）。

下面是您作为示例给出的范围的JavaScript实现——给定列表的内容实际上与此无关，只是它的大小(示例中n=5):

js prettyprint-override">let pairs = [[0, 2], [1, 4], [2, 3], [0, 3]];
let n = 5;

// Translate pairs to +1/-1 changes in result array
let result = Array(n+1).fill(0); // Add one more dummy entry
for (let pair of pairs) {
    result[pair[0]]++;
    result[pair[1] + 1]--; // after(!) the range
}
result.pop(); // ignore last dummy entry

// Accumulate changes from left to right
for (let i = 1; i < n; i++) {
    result[i] += result[i-1];
}

console.log(result);