Find the number of pairs in the array whose difference is K?

Question

So basically I'm trying to do this

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

with the exception of linear time, preferably with a single LINQ query and in a way that is compact, readable and micro-optimal. So I came up with an attempt

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)
        ); 
}

which continues to come out like 0, and I can’t understand why.

Let me explain how I think this works. If we have arr={1,1,1,2,3,3,5}and K=2, then it counterlooks like

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

Let count = 0.

I take the key 1and see that 1-K=-1it is not a key in counterand therefore count =0. 0. The same with the key 2.

3 3-K=1, counter. 3 1 (.. counter[3]=1 2 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

:

public int NumdiffLinear(int[] arr, int K)
        {
            var dupsDictionary =
                arr
                    .GroupBy(i => i)
                    .ToDictionary(g => g.Key, g => g.Count());


            return dupsDictionary.Keys.Aggregate(
                0,
                (total, i) =>
                    total +
                    dupsDictionary.Keys.Where(key => i - key == K)
                        .Sum(key => dupsDictionary[key]*dupsDictionary[i]));
        }

Answer 2

:

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();
}

Answer 3

(total, i) => total + counters[i] * (counters.ContainsKey(K - i) ? counters[K - i] : 0)

(total, i) => total + counters[i] * (counters.ContainsKey(i-K) ? counters[i-K] : 0)

Answer 4

. , , key = 1 K = 2. , key = (1+2).

In your algorithm, O (n ^ 2) you check J - I == K. Now suppose you have only Iand K. Simple math is simple J = K + I, if the condition is true, then it Jmust exist.

(total, i) => total + counters[i] * (counters.ContainsKey(K + i) ? counters[K + i] : 0)