Ниже приведена задача #268 из Leet Code. Я покажу мыслительный процесс, лежащий в основе моего решения, а также любой рефакторинг, который я сделал.

Учитывая массив, содержащий n различных чисел, взятых из 0, 1, 2, ..., n, найдите то, которое отсутствует в массиве.

Пример 1:

Input: [3,0,1]
Output: 2

Пример 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Примечание.
Ваш алгоритм должен работать с линейной сложностью во время выполнения. Не могли бы вы реализовать это, используя только постоянную сложность дополнительного пространства?

Входные данные, выходные данные, ограничения и пограничные случаи:

Для начала ввод состоял из массива различных чисел от 0 до n, в котором отсутствовало одно число и не было кратных. На выходе было отсутствующее число из массива. Например, для массива [0, 3, 2, 1, 5] отсутствующим числом будет 4. Ограничений не было, но возможность отсутствия пропущенных чисел рассматривалась как пограничный случай. Например, если задано [0,1], какое число будет считаться «отсутствующим» в выходных данных? После пары проб и ошибок стало понятно, что в случае отсутствия пропущенных чисел правильным выводом будет следующее число в последовательности. Например, если задано [0, 1, 2, 3, 4], правильным результатом будет 5.

Возможные методы:

Было много возможных подходов к этой проблеме, но я надеялся найти эффективный.

  1. Сортировка. Используя метод сортировки, массив будет переупорядочен от 0 до n. Оттуда можно перебрать массив, чтобы проверить, какой индекс не равен его элементу. Если нужно было проверить элемент в индексе 8 (то есть массив [8]), значение должно быть 8, но если было получено любое другое значение, например 9, то число 8 может быть возвращено как наше отсутствующее значение.
  2. Создание другого массива 0-n. Другой метод, который я рассмотрел, заключался в том, чтобы найти максимальное число в заданном массиве, а затем создать другой массив с диапазоном от 0 до n. Затем цикл for будет использоваться для перебора созданного массива, и с помощью метода .includes() будет возвращено не включенное число.
  3. Сокращение и математика. Используя сокращение по заданному массиву, можно вычислить общую сумму всех чисел в массиве. Длина заданного массива также является наибольшим числом в массиве. Например, в этом массиве: [0,2,4,1,3,7,6] длина === 7, что также является наибольшим числом в массиве. После быстрого поиска в гугле была найдена формула суммы всех чисел ниже N. Сравнив разницу в формуле сокращения с разницей в формуле суммы n, можно получить ответ. Это метод, которым я в конечном итоге следовал.

Объявленная в строке 2 переменная сумма использует длину заданного массива для вычисления предполагаемой суммы (подробнее об этой формуле). Затем функция сокращения используется с аккумулятором, равным 0, для сложения суммы заданного массива массивов. Затем возвращается разница между суммой и уменьшенным значением.