求数组中差异为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.

我拿钥匙1,看到它1-K=-1不是钥匙counter,因此count =仍然是0.与钥匙相同2.

对于3我们拥有的钥匙3-K=1是关键counter.存在3密钥1(即密钥的counter[3]=1两次出现2.因此,count = 3*2 = 6由于对(1,3),(1,3),(1,3),(1,3),(1,3), (1,3),(1,3)可以形成.

通过与上面相同的逻辑,我们再添加一个count因为对(3,5).所以答案是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();
}