我试着从Codility解决问题，
我们在飞机上画N个碟片。盘的编号从0到N-1。给出了N个非负整数的阵列A，指定了盘的半径。第J个圆盘的中心位于（J，0）和半径A [J]。
我们说如果J≠K则第J个盘和第K个盘相交，并且第J个和第K个盘具有至少一个公共点（假设盘包含它们的边界）。
下图显示了N = 6和A的光盘如下：
A[0] = 1
A[1] = 5
A[2] = 2
A[3] = 1
A[4] = 4
A[5] = 0
有十一对（无序）光盘相交，即：
圆盘1和圆盘4相交，并且都与所有其他圆盘相交;光盘2也与光盘0和3相交。写一个功能：
class Solution { public int solution(int[] A); }
如上所述，给定描述N个盘的阵列A，返回交叉盘的（无序）对的数量。如果交叉对的数量超过10,000,000，则该函数应返回-1。
给定上面所示的阵列A，该函数应返回11，如上所述。
假使，假设：
N是[0..100,000]范围内的整数;数组A的每个元素都是[0..2,147,483,647]范围内的整数。复杂：
预期的最坏情况时间复杂度为O（N * log（N））;预期的最坏情况空间复杂度是O（N）（不计算输入参数所需的存储空间）。
我也有一个我试图理解的解决方案，
public static int solution(int[] A) {
int N = A.length;
int[] sum = new int[N];
for (int i = 0; i < N; i++) {
int right;
if (N - 1 >= A[i] + i) {
right = i + A[i];
} else {
right = N - 1;
}
sum[right]++;
}
for (int i = 1; i < N; i++) {
sum[i] += sum[i - 1];
}
int result = N * (N - 1) / 2;
for (int j = 0; j < N; j++) {
int left;
if (j - A[j] < 0) {
left = 0;
} else {
left = j - A[j];
}
if (left > 0) {
result -= sum[left - 1];//.
}
}
if (result > 10000000) {
return -1;
}
return result;
}
虽然我部分理解了解决方案，但我无法完全理解它。我在下面描述，
一世。我们创建了一个长度为sum的数组N，并填充了光盘最右边的点作为索引。如果最右边的点大于N-1，我们将其设置为N-1
II。执行数组sum的前缀和，即扫描数字序列x0，x1，x2，...是数字y0，y1，y2，...的第二个序列，前缀（运行总数）的总和输入顺序：
x0 = x0
x1 = x0 + x1
x2 = x0 + x1+ x2
III。计算所提供数组的最大可能交集，即N * (N - 1) / 2
结果来自于选择2种元素的15种可能组合，即C(N,R)。如果R = 2，我们可以推导出C（N，R）= N！/ R！*（N-R）！到N * (N - 1) / 2
IV。找到最左边的点，如果值小于零，则将其设置为零。然后，如果左边的值大于零，则将其转换为结果中的索引和实体。
首先，我不明白最后一步是怎么回事。谁能解释得更好？我认为在最后一行result -= sum[left - 1]我们推断出这些对没有来自max possble的交集，现在我试图理解计算
解决方案背后的想法是complement，它很容易计算交叉点的总和，并且也不难获得未交叉对的总数。
然后我们提供您提供的解决方案，解决方案中有四个步骤：
N-1作为最右边）圆圈可以到达每个圆圈，这就是我们在第一个loop中所做的事情;loop中有多少不能相交;left = j - A[j];无法与当前圆相交的所有圆（可以相邻但不相交，这里的left是当前圆可以到达最左边的点）。 // count the rightmost point for each circle;
for (int i = 0; i < N; i++) {
int right;
if (N - 1 >= A[i] + i) {
right = i + A[i];
} else {
right = N - 1;
}
sum[right]++;
}
// summing up since `i` cannot be reached/intersected from the left, there is no way the `right-er` can;
for (int i = 1; i < N; i++) {
sum[i] += sum[i - 1];
}
// get the total amount of combinations;
int result = N * (N - 1) / 2;
for (int j = 0; j < N; j++) {
int left; // the leftmost point the current circle can reach;
if (j - A[j] < 0) { // avoid invalid;
left = 0;
} else {
left = j - A[j];
}
if (left > 0) { // if it's valid, sum[left-1] will be the un-intersected, subtract it;
result -= sum[left - 1];
}
}我为下面的解决方案提供了解释，
sum[i]存储0 to i (inclusive)中最右边点的光盘数量。如果i = N-1，那么它存储在0 to i or higher (inclusive)内的光盘数量0 to (left-1)中最右边的点数。因此，对于那个特定的光盘，没有可能与这些光盘交叉，我们需要从最大可能的交叉点中扣除计数。我们的目的是找到一个特定的光盘，它不相交的光盘数量。对于具有第j个索引的特定光盘，最左边的点将是j - A[j]，并且对于具有i（变量）的中心的所有光盘，如果i + A [i] <j-A [j]就足够了它将不相交。
就前缀数组而言，如果j是光盘的最左侧点，则它不会与总共sum[j-1]光盘相交。
如果最左边小于0，我们将其设置为0，如果光盘的最右边点大于N-1，我们将其设置为N-1。因为，如果最左边的点小于0，为了可交叉，相同光盘的最右边的点将在=> 0（=在点的情况下）。所以在比较光盘时不要难以处理，这个光盘将被考虑。当我们将最右边的点设置为N-1时，类似的逻辑适用于> N-1