Optimisation de cet algorithme C# (Différence K)

Question

Voici le problème que je suis en train de résoudre (c'est un problème type, pas un problème réel) :

Etant donné N nombres, [N<=10^5] nous devons compter le nombre total de paires de numéros. nombres qui ont une différence de K. [K>0 et K<1e9]

Format d'entrée : La première ligne contient N et K (entiers). La 2ème ligne contient N nombres de l'ensemble. Tous les N nombres sont assurés d'être distincts. Format de sortie : Un nombre entier disant le nombre de paires de nombres qui ont une différence K.

Sample Input #00:
5 2
1 5 3 4 2
Sample Output #00:
3
Sample Input #01:
10 1
363374326 364147530 61825163 1073065718 1281246024 1399469912 428047635 491595254 879792181 1069262793 
Sample Output #01:
0

J'ai déjà une solution (et je n'ai pas réussi à l'optimiser aussi bien que je l'espérais). Actuellement, ma solution obtient un score de 12/15 lorsqu'il est exécuté, et je me demande pourquoi je n'arrive pas à obtenir 15/15 (ma solution à un autre problème était loin d'être aussi efficace, mais elle a obtenu tous les points). Apparemment, le code est exécuté avec "Mono 2.10.1, C# 4".

Alors, quelqu'un peut-il penser à une meilleure façon d'optimiser cela davantage ? Le profileur VS indique qu'il faut éviter d'appeler String.Split et Int32.Parse. Les appels à Int32.Parse ne peuvent pas être évités, bien que je suppose que je pourrais optimiser la tokenisation du tableau.

Ma solution actuelle :

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace KDifference
{
   class Solution
   {
      static void Main(string[] args)
      {
         char[] space = { ' ' };

         string[] NK = Console.ReadLine().Split(space);
         int N = Int32.Parse(NK[0]), K = Int32.Parse(NK[1]);

         int[] nums = Console.ReadLine().Split(space, N).Select(x => Int32.Parse(x)).OrderBy(x => x).ToArray();

         int KHits = 0;

         for (int i = nums.Length - 1, j, k; i >= 1; i--)
         {
            for (j = 0; j < i; j++)
            {
               k = nums[i] - nums[j];

               if (k == K)
               {
                  KHits++;
               }
               else if (k < K)
               {
                  break;
               }
            }
         }

         Console.Write(KHits);
      }
   }
}

Answer 1

Suite à la réponse d'Eric, collez l'implémentation de la méthode Interscet ci-dessous, elle est O(n) :

private static IEnumerable<TSource> IntersectIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
{
    Set<TSource> set = new Set<TSource>(comparer);
    foreach (TSource current in second)
    {
        set.Add(current);
    }
    foreach (TSource current2 in first)
    {
        if (set.Remove(current2))
        {
            yield return current2;
        }
    }
    yield break;
}