1679. Max Number of K-Sum Pairs

LeetCode задача 1679

Задача

Вам дан массив чисел nums и целое число k. Задача — найти максимальное количество пар в массиве, сумма элементов которых равна k.

Подсказки

Используйте технику двух указателей(pointers) после сортировки массива для оптимизации поиска пар.

Подход

Центральная идея решения задачи заключается в использовании техники двух указателей для быстрого нахождения пар чисел с заданной суммой k. Прежде чем применить эту технику, массив сортируется в возрастающем порядке. Затем создаются два указателя: один, указывающий на начало массива, и второй — на конец. Двигая эти указатели в зависимости от суммы элементов, на которые они указывают, мы можем найти все пары с суммой k.

Алгоритм

1. Отсортируйте массив в возрастающем порядке.
2. Инициализируйте два указателя: p1 на начало массива и p2 на конец.
3. Пока p1 меньше p2:
   • Если nums[p1] + nums[p2] равно k, увеличьте счетчик на 1, и сдвиньте оба указателя.
   • Если сумма меньше k, сдвиньте p1 вправо.
   • Если сумма больше k, сдвиньте p2 влево.

Решение

def maxOperations(nums, k) -> int:
    c = 0
    p1 = 0
    p2 = len(nums) - 1

    nums.sort()

    while p1 < p2:
        s = nums[p1] + nums[p2]
        if s == k:
            c += 1
            p1 += 1
            p2 -= 1
        elif s < k:
            p1 += 1
        else:
            p2 -= 1
    
    return c