// Даны две отсортированных по неубыванию последовательности целых чисел.

Условие

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

// 0 <= N <= 10^6 // -10^9 <= a[i] <= 10^9

// [1] // [2, 3, 4, 5, 6] // [1]

// [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...] // [1] // [2, 3, 4, 5, 6, 7, 8]

func filter(first []int, second []int) []int { res := make([]int, 0, len(first))

i, j := 0, 0

for i < len(first) && j < len(second) {
    if first[i] < second[j] {
        result = append(result, first[i])
        i++
    } else if first[i] > second[j] {
        j++
    } else {
        i++
        j++
    }
}

for i < len(first) {
    result = append(result, first[i])
    i++
}

return result

}

Ответ

В представленном коде на Go есть ошибка: переменная result не объявлена, а используется res. Нужно использовать одну и ту же переменную.

Исправленный вариант функции, которая возвращает элементы из первой отсортированной последовательности, которых нет во второй:

func filter(first []int, second []int) []int {
    res := make([]int, 0, len(first))

    i, j := 0, 0

    for i < len(first) && j < len(second) {
        if first[i] < second[j] {
            res = append(res, first[i])
            i++
        } else if first[i] > second[j] {
            j++
        } else {
            i++
            j++
        }
    }

    for i < len(first) {
        res = append(res, first[i])
        i++
    }

    return res
}

Идея алгоритма:

• Используем два указателя i и j для обхода обеих последовательностей.
• Если элемент из first меньше элемента из second, значит его нет во второй последовательности — добавляем в результат.
• Если элемент из first больше, двигаем указатель j во второй последовательности.
• Если равны — пропускаем оба.
• После окончания цикла добавляем оставшиеся элементы из first.

Алгоритм работает за O(N), что эффективно для больших массивов.