时间戳

首页 > 解决方案 > 数组元素总和的索引总和（优化）

java - 数组元素总和的索引总和（优化）

问题描述

你开始没有。元素假设 N，您将获得 N 个数字，下一行有一个空格。确定该数组中的案例数，使其遵循以下规则 -i+j=array[i]+array[j]其中 i 和 j 是索引和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);

标签： javapythonalgorithmoptimization

解决方案

首先注意条件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 occurrence (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

现在我们的目标可以通过将 entry 中的每个索引与 key-n以及entry 中的每个索引相结合来实现n。我们需要对每一对进行排序，以便满足另一个条件i < j。这始终是可能的，因为相同的索引不会同时被计算为正数和负数。因此，映射条目n的对数是负数和正数两次计数的乘积。在您的情况下，您只有一个n，在其他情况下可能有很多，因此将它们中的对数加在一起。在示例中，我们只有 2 * 2 = 4 对。这个结果与你的问题一致。

编辑：复杂性考虑：我的方法的复杂性取决于地图操作的复杂性，而这又取决于您选择的地图实现。对于大多数地图实现，地图的构建将是耗时的部分，并且需要 O(n * 地图查找成本)。假设 a 中的查找HashMap介于线性和 O(log n) 之间，您可以得到介于 O(n) 和 O(n * log n) 之间的结果。在任何情况下都比你的 O(n ^ 2) 好。

我最初的想法

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

将索引存储到多重映射或列表映射中，其中计算的差异是键。在示例中，您将获得

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

现在我们的目标可以通过将 entry 中的每个索引与 key-n以及entry 中的每个索引相结合来实现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 对，只是顺序不同。如果重要，排序将解决这个问题。

推荐阅读