Учитывая массив целых чисел и целое число, верните индексы двух чисел так, чтобы они складывались.

Вы можете предположить, что каждый вход будет иметь ровно одно решение, и вы не можете использовать один и тот же элемент дважды.

Вы можете вернуть ответ в любом порядке.

Пример 1:

Input: nums = [2,7,11,15], target = 9 Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Пример 2:

Input: nums = [3,2,4], target = 6 output: [1,2]

Пример 3:

Input: nums = [3,3], target = 6 output: [0,1]

Моя первоначальная мысль при рассмотрении этой проблемы состояла в том, чтобы использовать подход с двумя указателями curr и next, проверить, соответствуют ли они цели, если да, я верну их индексы. в противном случае я буду перемещать curr и next соответственно, чтобы сделать то же самое для следующих значений.

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

Я исследовал другие подходы и решил вместо этого использовать хэш-карту для хранения элементов, сопоставить их с соответствующими индексами, а затем проверить, присутствует ли разница между целью и элементом в хэш-карте, если да, я бы вернул текущий индекс элемента и значение дополнение в хэш-карте, иначе я бы добавил их в хэш-карту:

  • Создать пустую хэш-карту
  • Перебрать входной массив nums
  • Для каждого элемента в nums вычислите его дополнение, вычитая его из цели
  • Проверьте, существует ли дополнение в хэш-карте
  • Если дополнение существует, вернуть массив, содержащий индекс текущего элемента и значение дополнения в хэш-карте.
  • Если дополнение не существует, добавьте текущий элемент и его индекс в хэш-карту.
  • Если дополнение не найдено, вернуть false

Получив зеленую галочку, я отправил код в LeetCode и вот статистика:

Это решение превосходит 95% всех представлений для времени выполнения и 39% для памяти, что совсем неплохо, особенно для времени выполнения, но идея использования двух указателей для решения этой проблемы просто не покидала меня. кроличью нору, чтобы найти решение, использующее этот подход.

Я узнал довольно много идей в кроличьей норе, но прежде чем я поделюсь ими, давайте рассмотрим решение этой проблемы с использованием подхода с двумя указателями:

  • Инициализируйте два указателя, один в начале массива (левый указатель) и один в конце массива (правый указатель).
  • Пока левый указатель меньше правого, сделайте следующее:
  • а. Вычислите сумму значений левого и правого указателя.
  • б. Если сумма равна цели, верните индексы двух чисел в качестве решения.
  • в. Если сумма меньше целевой, переместите левый указатель вправо на единицу.
  • д. Если сумма больше целевой, переместите правый указатель влево на единицу.
  • Если решение не найдено, вернуть пустой массив или нулевое значение.

После запуска кода я понял, что это решение не работает в тестовом примере 2:

Это было первое понимание из кроличьей норы, тестовый пример 2 терпит неудачу, потому что входной массив [3, 2, 4] не отсортирован, поэтому значения не находятся в правильном порядке, чтобы сумма равнялась целевому значению.

Подход с двумя указателями лучше всего работает, только если входной массив уже отсортирован!

Поэтому я пересмотрел свои шаги, чтобы сначала отсортировать массив, а затем использовать два указателя, но он все еще не очищал этот тестовый пример, потому что теперь возвращаемые индексы не совпадают с индексами в исходном входном массиве:

Элементы, которые складываются в цель, — это элемент с индексом 1 (2) и элемент с индексом 2 (4), но после сортировки массива элемент с индексом 1 равен 3, а элемент с индексом 2 равен 4, поэтому функция возвращает [0, 2] вместо [1, 2], что является правильным ответом.

Поскольку функция sort() сортирует массив на месте, я решил отсортировать копию входного массива вместо оригинала, и когда я найду два элемента, которые складываются в цель, я верну их индексы из исходного ввода. массив числа:

На этот раз решение действительно прошло тестовый пример 2, а также тестовый пример 1, однако тестовый пример 3 теперь терпел неудачу… какое-то время я не мог понять, почему, пока не обнаружил, что, хотя я уверен, что возвращаю индексы из оригинала входного массива, indexOf() будет возвращать только индекс первого вхождения элемента, поэтому в этом случае вывод будет [0, 0] вместо [0, 1], что является правильным ответом, это было еще одно понимание из кроличьей норы:

Подход с двумя указателями лучше всего работает, только если значения во входном массиве уникальны!

Таким образом, использование двух указателей является оптимальным решением только тогда, когда ввод массива отсортирован, а элементы массива уникальны. Это были не единственные идеи, которые я вытащил из кроличьей норы, но для целей этой статьи их должно быть достаточно.

Я думал о том, как решить, чтобы иметь возможность возвращать индексы всех вхождений элементов, но это потребовало бы еще большего объема памяти и времени для отслеживания дубликатов, поэтому я решил, по крайней мере, на данный момент оставить свой случай, что Two Pointer подход не является действенным решением этой проблемы.

В заключение, временная сложность подхода с двумя указателями составляет O(n), а сложность памяти составляет O(1 ) в то время как временная сложность использования Hashmap составляет O(n), а сложность памяти составляет O(n).

Что касается временной сложности, то и подход с двумя указателями, и подход Hashmap имеют линейную сложность O(n).

С точки зрения сложности памяти, метод Два указателя имеет постоянную сложность памяти O(1), поскольку он использует только фиксированное количество переменных. (два указателя) независимо от размера ввода. С другой стороны, подход Hashmap имеет линейную сложность памяти O(n), поскольку он использует структуру данных (hashmap), которая хранит одно значение для каждого элемента входного массива.

В целом подход Два указателя более эффективен с точки зрения памяти, чем подход Hashmap, но оба они подходят для решения этой задачи с линейной временной сложностью. Это действительно сводится к требованиям проблемы, если память не имеет большого значения, вы можете использовать подход Hashmap, но если память является проблемой, подход с двумя указателями больше подходит. оптимальный.

Другое название алгоритма двух указателей — алгоритм скользящего окна. Это называется скользящим окном, потому что в нем участвуют два указателя, которые «скользят» по массиву, перемещаясь друг к другу или отдаляясь друг от друга, в зависимости от конкретной проблемы, которую вы пытаетесь решить.

Два указателя определяют окно или подраздел массива, и алгоритм работает, поддерживая инвариант, согласно которому значения в окне соответствуют желаемому условию, например, нахождение суммы определенной цели или подсчета отдельных элементов в этом окне.

Первоначально опубликовано на http://codemghrib.wordpress.com 23 января 2023 г.