javascript - HackerRank 上的配对算法

Question

让我快速解释一下问题

最初来自这里:https://www.hackerrank.com/challenges/pairs

示例输入是:

5 2  
1 5 3 4 2

引用上述输入

第一行:

N = 5, K = 2 

其中 N 是集合中整数的数量，K 是我们要寻找的差值

第二行(作为数组):

[1, 5, 3, 4, 2];

数组中有多少对相差 K？

示例答案:“集合中有 3 对整数，相差 2。”

我正在为此努力，但我遗漏了一些东西:

function findDifference(k, nArr) {

    nArr.sort((a, b) => a - b);

var pairsWithDifferenceOfK = 0;

for (var i = 0; i < nArr.length; i++) {
    if (Math.abs((nArr[i] - ((nArr.length > (i + k)) ? nArr[(i + k)] : nArr[i]))) === k) {
       pairsWithDifferenceOfK++;
   };
}
   console.log(pairsWithDifferenceOfK);
}
var K = 2;
Arr = [1, 5, 3, 4, 2];
findDifference(K, Arr);

输出:

3

在给定这些输入时会失败(我很好奇为什么在某些输入上会失败，而在其他输入上却不会):

10 1
363374326 364147530 61825163 1073065718 1281246024 1399469912 42804763 491595254 879792181 1069262793

Answer 1

解决这个问题的一种方法是使用递归。在函数的每次迭代中，您可以获取第一个元素，然后将其与其余元素进行比较。例如，你从

开始

var rest = arr.splice(1);

其中 rest 是 [5, 3, 4, 2] 并且您将每个元素与 1 进行比较，然后将 rest 传递给函数将 [3, 4, 2] 与 5 等进行比较...然后检查每个元素的差异是否为 k 以及是否为你是增加结果吗？当arr参数为空数组函数将退出或返回1。

var K = 2;
var array = [1, 5, 3, 4, 2];

function findDifference(k, arr) {
  var r = 0;

  function inner(k, arr) {
    if (!arr.length) return 1;
    var rest = arr.splice(1);

    rest.forEach(function(e) {
      if (Math.abs(arr[0] - e) == k) r++;
    })

    inner(k, rest);
  }
  inner(k, arr);
  return r;
}

console.log(findDifference(K, array));