确定总和到数组中的某些值的整数对

-1

我有计算N个整数对的数目的总和为value的程序数。为了简化问题，还假定整数是不同的。确定总和到数组中的某些值的整数对

l.Sort(); 
for (int i = 0; i < l.Count; ++i) 
{ 
    int j = l.BinarySearch(value - l[i]); 
    if (j > i) 
    { 
     Console.WriteLine("{0} {1}", i + 1, j+1); 
    } 
}

为了解决这个问题，我们对数组进行排序（以启用二进制搜索），然后，对阵列中的每个条目a[i]，为value - a[i]做一个二进制搜索。如果结果是j与j > i索引，我们将显示这一对。

但这种算法没有在接下来的输入工作：

1 2 3 4 4 9 56 90因为j总是比i小。

如何解决这个问题？

来源

2015-11-07 Anatoly

在你的输入中，你看到总和为0的对吗？ – Leeor

看起来他希望这两个对的总和为“value”，不一定是0. –

@TomZych是的，修正了它 – Anatoly

我会走更高效的解决方案，需要更多的空间。

假设数字并不明显

与整数作为一个键和一个频率，在这个哈希表中的值
迭代创建一个哈希表。
对于每个键
- 计算差异diff = value - k
- 在散列
- 查找用于diff如果存在匹配检查，如果该值已经得到频率> 0
- 如果频率是> 0递减它由1个产量电流对k, diff

下面是一个Python代码：

def count_pairs(arr, value): 
    hsh = {} 
    for k in arr: 
    cnt = hsh.get(k, 0) 
    hsh[k] = cnt + 1 
    for k in arr: 
    diff = value - k 
    cnt = hsh.get(diff) 
    if cnt > 0: 
     hsh[k] -= 1 
     print("Pair detected: " + str(k) + " and " + str(diff)) 

count_pairs([4, 2, 3, 4, 9, 1, 5, 4, 56, 90], 8) 
#=> Pair detected: 4 and 4 
#=> Pair detected: 3 and 5 
#=> Pair detected: 4 and 4 
#=> Pair detected: 4 and 4

至于counts the number of pairs是非常模糊的描述，在这里你可以看到4个不同的（以数量的指标）对。

来源

2015-11-07 12:59:31 fl00r

如果您希望此为非 -distinct值工作（这你问题不说，但您的评论暗示），二进制搜索仅i之后阵列的部分。这也消除了对测试的需要。

会显示代码，但我不知道如何在中指定您使用的任何语言的这种切片。

来源

2015-11-07 12:42:39

确定总和到数组中的某些值的整数对

回答

相关问题