数组元素之和的索引和（优化）

Question

你没有开始。如果元素为N，则在下一行中为您提供N个数字和空格。确定该数组中的个案数，使其遵循以下规则 - i+j=array[i]+array[j]，其中i和j是index和i<j。

例如，输入 -

5
1 0 2 4 3

输出 -

4

说明-

Elements of array at index (0,1), (1,3), (3,4) and (0,4) follows the above rule

现在，我可以通过遍历所有元素使用O（n * n）来解决它。你能想出优化的代码吗？

我在python中的代码如下：

n=int(input())
arr=list(map(int,input.split(' ')))
count=0
for i in range(n):
    for j in range(i+1,n):
        if(i+j==arr[i]+arr[j]):
            count+=1
print(count)

我在Java（代码段）中的代码如下：

int n=sc.nextInt(); //sc is scanner
int a[]=new int[n];
for(int i=0;i<n;i++)
{
  a[i]=sc.nextInt();
}
int count=0;
for(int i=0;i<n;i++)
{  for(int j=i+1;j<n;j++)
       if(i+j==a[i]+a[j])
          count++;
}
System.out.println(count);

Answer 1

首先注意条件i+j=array[i]+array[j]相当于：

(array[i] - i) + (array[j] -- j) == 0

因此，为每个array[i] - i计算i。在你的例子中，你将得到[1, -1, 0, 1, -1]。编辑：感谢maaartinus的评论，因为只要求对的计数，我们也只需要计算每个计算的差异。因此，对于每个差异，存​​储它作为正面差异发生的次数和作为负面的多少次。使用计算差异的地图作为关键：

   0 -> 1 occrurrence (index 2)
   1 -> 2 negative occurrences (indices 1, 4), 2 positive occurrences (indices 0, 3).

没有存储具体的索引，我只将它们作为解释。并且不要存储0条目。由于i < j限制，我们不能用它做任何事情。所以在你的例子中我们只有：

   1 -> 2 negative occurrences, 2 positive occurrences

现在我们的目标可以通过将条目中的每个索引与关键-n和条目n中的每个索引相结合来实现。我们需要对每一对进行排序，以便满足另一个条件i < j。这总是可行的，因为相同的指数不会被计为正数和负数。因此，来自地图的条目n的对的数量是两个负面和正面事件计数的乘积。在你的情况下你只有一个n，在其他情况下可能有很多，所以从它们一起添加对的数量。在这个例子中，我们只有2 * 2 = 4对。此结果与您的问题一致。

编辑：复杂性考虑：我的方法的复杂性取决于地图操作的复杂性，而地图操作的复杂性又取决于您选择的地图实现。对于大多数地图实现，地图的构造将是耗时的部分，并且将花费O（n *地图查找的成本）。假设在HashMap中的查找介于线性和O（log n）之间，您可以在O（n）和O（n * log n）之间得到一些东西。在任何情况下都比你的O（n ^ 2）更好。

快乐的编码。

我原来的想法

我最初的想法是生成所有对。这个想法可能更容易理解，所以我让它站在这里。但它的表现并不比O（n ^ 2）好。

将索引存储到多个映射或列表映射中，其中计算的差异是键。在这个例子中你会得到

  -1 -> 1, 4
   0 -> 2
   1 -> 0, 3

现在我们的目标可以通过将条目中的每个索引与关键-n和条目n中的每个索引相结合来实现。只有我们需要对每一对进行排序，以便满足另一个条件i < j（这总是可行的，因为相同的索引不在两个列表中）。

未排序的对：

(1, 0), (1, 3), (4, 0), (4, 3)

排序对（即i < j）：

(0, 1), (1, 3), (0, 4), (3, 4)

为了比较，在纠正自己的代码后产生：

(0, 1), (0, 4), (1, 3), (3, 4)

它们是相同的4对，只是顺序不同。如果重要的话，排序将解决这个问题。