Метод скользящего окна или двух указателей

Метод двух указателей (или двух индексов) - это популярная техника в программировании, которая используется для решения задач, связанных с последовательностями данных (массивами, строками и т.д.). Основная идея метода заключается в использовании двух указателей (или индексов), которые перемещаются по последовательности данных для достижения определенной цели.

Пары чисел в отсортированном массиве

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

fun findPairsWithSum(arr: IntArray, target: Int): List<Pair<Int, Int>> {
    val result = mutableListOf<Pair<Int, Int>>()
    var left = 0
    var right = arr.size - 1

    while (left < right) {
        val sum = arr[left] + arr[right]
        when {
            sum == target -> {
                result.add(Pair(arr[left], arr[right]))
                left++
                right--
            }
            sum < target -> left++
            else -> right--
        }
    }

    return result
}

fun main() {
    val arr = intArrayOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
    val target = 10
    val pairs = findPairsWithSum(arr, target)
    println("Пары чисел, сумма которых равна $target: $pairs")
}

Объяснение

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

Уникальные тройки

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

fun threeSum(nums: IntArray): List<List<Int>> {
// Сортируем массив, чтобы использовать метод двух указателей
nums.sort()

// Список для хранения уникальных троек
val result = mutableListOf<List<Int>>()

// Проходим по индексам массива nums
for (i in nums.indices) {
    // Пропускаем дубликаты, если текущий элемент такой же, как предыдущий
    if (i > 0 && nums[i] == nums[i - 1]) continue

    // Указатель, начинающийся сразу после i
    var left = i + 1
    // Указатель, начинающийся с конца массива
    var right = nums.size - 1

    // Пока left меньше right
    while (left < right) {
        // Сумма текущих трех элементов
        val sum = nums[i] + nums[left] + nums[right]

        // Если сумма равна 0, добавляем тройку в результат
        if (sum == 0) {
            result.add(listOf(nums[i], nums[left], nums[right]))

            // Пропускаем все дубликаты nums[left]
            while (left < right && nums[left] == nums[left + 1]) left++
            // Пропускаем все дубликаты nums[right]
            while (left < right && nums[right] == nums[right - 1]) right--
            
            // Сдвигаем указатели left и right
            left++
            right--
        } else if (sum < 0) {
            // Если сумма меньше 0, увеличиваем left для увеличения суммы
            left++
        } else {
            // Если сумма больше 0, уменьшаем right для уменьшения суммы
            right--
        }
    }
}

// Возвращаем список уникальных троек, сумма которых равна 0
return result
}

Объяснение

  1. Сортировка массива:
    • Сначала сортируем массив. Сортировка позволяет нам эффективно использовать метод двух указателей.
  2. Итерация по массиву:
    • Проходим по каждому элементу массива, используя индекс i как первый элемент потенциальной тройки.
    • Пропускаем дубликаты, чтобы не учитывать одни и те же тройки несколько раз.
  3. Инициализация указателей:
    • left указывает на элемент сразу после i.
    • right указывает на последний элемент массива.
  4. Основной цикл:
    • Пока left меньше right, вычисляем сумму элементов nums[i], nums[left], nums[right].
    • Если сумма равна 0, добавляем тройку в результат, сдвигаем оба указателя и пропускаем дубликаты.
    • Если сумма меньше 0, сдвигаем left вправо, чтобы увеличить сумму.
    • Если сумма больше 0, сдвигаем right влево, чтобы уменьшить сумму.
  5. Пропуск дубликатов:
    • После нахождения тройки, равной 0, мы сдвигаем указатели и пропускаем все последующие дубликаты.
  6. Вывод результатов:
    • После завершения всех итераций возвращаем список уникальных троек, сумма которых равна 0.

Пример выполнения

Для входного массива intArrayOf(-1, 0, 1, 2, -1, -4) отсортированный массив будет [-4, -1, -1, 0, 1, 2]. Метод найдет следующие тройки:

  • [-1, -1, 2]
  • [-1, 0, 1]

Таким образом, результат будет [[−1, -1, 2], [-1, 0, 1]].