All problems

Max Number of K-Sum Pairs

Medium · two pointers

You are given a list of integers nums and an integer k.

In one operation you choose two numbers from the list whose sum is exactly k, and remove both of them from the list. Each number can be removed only once, so it can belong to at most one operation. Two copies of the same value count as two different numbers.

Return the largest number of operations you can perform.

Examples

Example 1

Input: nums = [1, 2, 3, 4], k = 5

Output: 2

Remove 1 and 4, then remove 2 and 3.

Example 2

Input: nums = [3, 1, 3, 4, 3], k = 6

Output: 1

Remove two of the 3s. The 1 and the 4 have no partners left, and the third 3 has no partner.

Example 3

Input: nums = [2, 2, 2], k = 4

Output: 1

Two of the three 2s can be removed together. One 2 is left over.

Constraints