Два указателя

Представьте два списка гостей, каждый по алфавиту, и их нужно свести в один. Никто не станет перемешивать всех гостей и сортировать заново. Удобнее положить по пальцу на начало каждого списка. Каждый раз вы выписываете то имя, что раньше по алфавиту, и сдвигаете палец с него на строку вниз.

В Go та же задача — слить два отсортированных среза в один, тоже отсортированный. Можно собрать все числа в один срез и отсортировать его функцией slices.Sort:

package main

import (
    "fmt"
    "slices"
)

func main() {
    a := []int{1, 4, 6}
    b := []int{2, 3, 7}
    all := append([]int{}, a...)
    all = append(all, b...)
    slices.Sort(all)
    fmt.Println(all) // [1 2 3 4 6 7]
}

Давайте разберём пример по строкам:

1. all := append([]int{}, a...) копирует числа из a в новый срез.
2. all = append(all, b...) дописывает к ним числа из b.
3. slices.Sort(all) сортирует все шесть чисел, и программа печатает [1 2 3 4 6 7].

Результат верный, но сортировка не учитывает, что обе половины уже упорядочены, и переставляет все числа заново. Слияние справляется за один проход по обоим срезам — как два пальца по двум спискам.

Два индекса

Метод двух указателей — проход по данным двумя индексами, каждый из которых сдвигается отдельно.

Указатель здесь — обычная переменная int с номером элемента, а не указатель Go с * и &. Палец лежит на строке списка, а не хранит её адрес.

Слияние

При слиянии каждый индекс отвечает за свой срез:

• индекс i идёт по a;
• индекс j идёт по b;
• на каждом шаге меньшее из a[i] и b[j] (при равенстве — любое из них) уходит в результат, и сдвигается только его индекс.

Для срезов из примера выше шаги такие:

Нажмите «Следующий шаг» и пройдите то же слияние в программе: следите за i и j в рамке main — за шаг сдвигается только один из них.

Каждый шаг отправляет в результат одно число, поэтому слияние срезов длиной n и m занимает не больше n + m шагов.

Хвосты после цикла

После пятого шага срез a закончился, а в b осталось 7. С таким остатком поступают так:

1. Хвост уже отсортирован и больше всего, что попало в результат.
2. Поэтому его дописывают целиком: append(out, b[j:]...).
3. Какой срез закончится первым, зависит от данных, поэтому после цикла дописывают оба хвоста, a[i:] и b[j:]: пустой ничего не добавит.

Где встречается приём

Этот приём часто встречается на собеседованиях:

• слияние — главный шаг сортировки слиянием;
• двумя указателями решают много задач на отсортированных данных.

Общие элементы

Тем же проходом находят числа, которые есть в обоих отсортированных срезах:

a, b := []int{1, 3, 4, 8}, []int{2, 3, 8, 9}
var common []int
i, j := 0, 0
for i < len(a) && j < len(b) {
    if a[i] < b[j] {
        i++
    } else if a[i] > b[j] {
        j++
    } else {
        common = append(common, a[i])
        i++
        j++
    }
}
fmt.Println(common) // [3 8]

Цикл идёт, пока оба индекса внутри своих срезов. Меньшее число не встретится в другом срезе дальше: там стоят только большие. Поэтому на каждом шаге возможны три случая:

• a[i] < b[j] — сдвигается i;
• a[i] > b[j] — сдвигается j;
• числа равны — число попадает в common, и сдвигаются оба индекса.

Давайте пройдём первые шаги:

1. 1 < 2 сдвигает i.
2. 3 > 2 сдвигает j.
3. 3 и 3 равны и уходят в common.

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

Частая ошибка

Условие цикла пишут через ||, чтобы дойти до конца обоих срезов:

a := []int{1, 2}
b := []int{5}
i, j := 0, 0
for i < len(a) || j < len(b) { // ✗
    if a[i] < b[j] {
        i++
    } else {
        j++
    }
}

panic: runtime error: index out of range [2] with length 2

Индекс выходит за конец среза:

1. Когда a закончился, цикл продолжается ради b.
2. Цикл читает a[2] за концом среза: палец съехал со списка.
3. Программа останавливается с паникой.

Оставьте в условии &&, а остаток другого среза обработайте после цикла: при слиянии его дописывают через append.

Главное

• Два указателя — два индекса int, которые идут по данным и сдвигаются независимо.
• Слияние двух отсортированных срезов: в результат уходит меньшее из a[i] и b[j], а после цикла дописывают оба хвоста.
• Слияние занимает не больше n + m шагов вместо новой сортировки всех чисел.
• Условие цикла — &&: с || индекс выходит за конец среза, и программа паникует.