c - 优化给定总和的数组中对的索引

Question

我正在编码以查找数组中一对数字的所有索引，该数组的总和已给定。

for(i=0;i<max;i++)
{
    for(j=i+1;j<max;j++)
    {
        if(a[i]+a[j]==sum)
            printf("%d %d\n",i,j);
    }
}

其中 max 是数组的最大大小。 sum 是一对数字的总和。(数组中的值可能重复。)

但我只得到了这个天真的 O(n^2) 解决方案。任何人都可以帮助我为这种情况获得最佳解决方案。

Answer 1

• 对数组进行排序。 O(nlg(n))

• 对于数组 O(n) 中的每个 i，进行二进制搜索 sum-i O (lg(n)) 总共 O(nlg(n))

O(nlg(n)) 的 2 个操作，总共 O(nlg(n))