int k_paired(const std::vector<int>& arr, const int k)
{
  size_t i = 0,j = 1,res = 0;
  while(i<arr.size() && j<arr.size())
  {
     if (i != j && arr[j]-arr[i] == k)
     {
        res++;
        i++;
        j++;
     }
     else if(arr[j]-arr[i]<k)
        j++;
     else
        i++;
  }
   return res;
}

Creo es una variante ligeramente mas rapida que las anteriores segun las mediciones que realize @loretz estaria interesante ver tu solucion.