Напишите функцию, чтобы определить, содержит ли массив последовательные числа хотя бы для N чисел

Question

Я пытаюсь написать функцию, чтобы определить, содержит ли массив последовательные числа хотя бы для N чисел. Например, вводом является [1,5,3,4] и 3, получается true, потому что массив имеет 3 последовательных чисел, что составляет [3,4,5]

Здесь эта функция требует предварительной сортировки, и это не самое красноречивое на мой взгляд решение. Может кто-нибудь взглянуть и сделать некоторые улучшения в этом?

function hasConsecutiveNums(array, N) {
  if (array.length < N) return false;
  if (N === 0) return true;
  const sortedArray = array.slice().sort((a, b) => a - b);
  let count = 0;
  let prev = null;
  for (const num of sortedArray) {
    if (prev && num === prev + 1) {
      count++;
    } else {
      count = 1;
    }
    if (count === N) return true;
    prev = num;
  }

  return false;
}

console.log(hasConsecutiveNums([1, 4, 5, 6], 3)) // true
console.log(hasConsecutiveNums([1, 4, 5, 6], 4)) // false

Answer 1

Сортировка массива сначала неплоха, но ваша программа разбита дубликатами и возвращает false для ([4, 5, 5, 6], 3). Это легко исправить.

Сортировка сначала занимает O (N log N) времени. Вы можете сделать это в ожидаемое время O (N), но метод более сложный и, вероятно, будет быстрее только для очень больших входных данных.

Он работает так:

1. Создать структура данных непересекающегося набора: https://en.wikipedia.org/wiki/Disjoint-set_data_structure
2. Итерация по массиву, сопоставление каждого уникального целого числа, которое вы найдете с набором в этой структуре.
3. При добавлении нового целое число, если наборы существуют для предыдущих и последующих целых чисел, затем объедините их с новым.
4. Когда вы закончите, найдите размер наибольшего набора, который представляет наибольшую последовательность последовательных чисел.

Answer 2

Вы можете внести некоторые изменения

• инициализировать prev с помощью undefined (null действует как нулевое число, если вы добавляете число), это позволяет
• опустить проверить с помощью prev
• переместить проверку на счетчик в первом операторе if и выйти досрочно, если найден желаемый приращенный счетчик.

function hasConsecutiveNums(array, N) {
  if (array.length < N) return false;
  if (N === 0) return true;
  const sortedArray = array.slice().sort((a, b) => a - b);
  let count = 0;
  let prev = undefined;
  for (const num of sortedArray) {
    if (num === prev + 1) {
      if (++count === N) return true;
    } else {
      count = 1;
    }        
    prev = num;
  }
  return false;
}

console.log(hasConsecutiveNums([1, 4, 5, 6], 3)) // true
console.log(hasConsecutiveNums([1, 4, 5, 6], 4)) // false