Максимальное количество пар K-суммы

Средняя

02 May 2024

Описание задачи #

Вам дан целочисленный массив nums и целое число k.

За одну операцию вы можете выбрать из массива два числа, сумма которых равна k, и удалить их из массива.

Верните максимальное количество операций, которые вы можете выполнить с массивом.

Ограничения #

Длина массива находится в диапазоне от 1 до 10⁵
Каждый элемент массива может принимать значение в диапазоне от 1 до 10⁹
k находится в диапазоне от 1 до 10⁹

Примеры #

Входные данные: nums = [1,2,3,4], k = 5

Ответ: 2

Пояснение: Вы можете удалить две пары чисел: (1,4) и (2,3), сумма которых равна 5.
Входные данные: nums = [3,1,3,4,3], k = 6

Ответ: 1

Пояснение: Вы можете удалить одну пару чисел: (3,3), сумма которых равна 6.

Решение #

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

Запускаем цикл по всем элементам массива и для каждого числа рассчитываем разность diff между k и текущим числом num.

Если в объекте digits уже есть запись для diff, это означает, что ранее было найдено число, которое в сумме с текущим числом num даст k. Если это так, то уменьшаем количество доступных чисел diff на единицу, и счетчик пар res увеличивается на один, так как найдена новая пара.

Если же такого числа нет, то текущее число num добавляется в digits, увеличивая счетчик количества этого числа на единицу, чтобы в будущем его можно было использовать для создания пары с другим числом.

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

Реализация #

package max_number_of_k_sum_pair

func maxOperations(nums []int, k int) int {
	digits := make(map[int]int)
	res := 0

	for _, num := range nums {
		diff := k - num

		if val := digits[diff]; val > 0 {
			digits[diff]--
			res++
		} else {
			digits[num]++
		}
	}

	return res
}

export const maxOperations = (nums: number[], k: number): number => {
    const digits: Record<number, number> = {}
    let res = 0

    for (const num of nums) {
        const diff = k - num

        if (digits[diff] > 0) {
            digits[diff] = (digits[diff] || 0) - 1
            res++
        } else {
            digits[num] = (digits[num] || 0) + 1
        }
    }

    return res
}

Оценка сложности #

По времени

Сложность O(n), так как мы итерируемся по всем элементам массива.

По памяти

Сложность O(n), так как создается хеш-таблица для хранения частот.

Оригинал задачи на Leetcode

Algorithmics