c# - 找出差为 K 的数组中的对数？

Question

所以基本上我想做的是

static int NumdiffExponential(int[] arr, int K)
{
    return (from i in arr
            from j in arr
            where (j - i) == K
            select 1).Count();
}

线性时间除外，最好使用单个 LINQ 查询，并以紧凑、可读和微优化的方式进行。所以我想到的就是尝试

static int NumdiffLinear(int[] arr, int K)
{
    var counters = 
        arr
        .GroupBy(i => i)
        .ToDictionary(g => g.Key, g => g.Count());
    return 
        counters
        .Keys
        .Aggregate(
            0, 
            (total, i) => total + counters[i] * (counters.ContainsKey(K - i) ? counters[K - i] : 0)
        ); 
}

一直显示为 0，我不明白为什么。

让我解释一下我认为它是如何工作的。如果我们有 arr={1,1,1,2,3,3,5} 和 K=2，那么 counter 是喜欢

1->3, 2->1, 3->2, 5->1 

让 count = 0。

我使用 key 1 并发现 1-K=-1 不是 counter 中的 key ，因此 count =0 仍然。与键 2 相同。

对于键 3，我们有 3-K=1，它是 counter 中的键。键 1 出现了 3 次(即 counter[3]=1 和键 2 出现了 2 次>. 因此 count = 3*2 = 6 因为对 (1,3),(1,3),(1,3),(1,3),(1,3) ,(1,3),(1,3)可以组成。

按照与上面相同的逻辑，由于对 (3,5)，我们在 count 中增加了一个。所以答案是 count = 7。

我的算法或它的实现有什么问题吗？

Answer 1

更具可读性和更紧凑:

static int NumdiffLinear(int[] arr, int K)
{
    return arr.SelectMany(v => arr, (a, b) => new { a, b })
                .Where(s => s.b - s.a == K)
                .Count();
}

下面是一个线性的，原理相同:

static int NumdiffLinear(int[] arr, int K)
{
    int n = 1;
    return arr.Select(value => new { value, index = n++ }) //Get number and index
                .SelectMany(indexValue => arr.Skip(indexValue.index), (a, b) => new { a = a.value, b }) //Project it with the next elements in the array
                .Where(s => s.a - s.b == K) //Do the math
                .Count();
}