1679. Max Number of K-Sum Pairs

Problem

You are given an integer array nums and an integer k.

In one operation, you can pick two numbers from the array whose sum equals k and remove them from the array.

Return the maximum number of operations you can perform on the array.

Example 1:

Input: nums = [1,2,3,4], k = 5
Output: 2
Explanation: Starting with nums = [1,2,3,4]:
- Remove numbers 1 and 4, then nums = [2,3]
- Remove numbers 2 and 3, then nums = []
There are no more pairs that sum up to 5, hence a total of 2 operations.

Example 2:

Input: nums = [3,1,3,4,3], k = 6
Output: 1
Explanation: Starting with nums = [3,1,3,4,3]:
- Remove the first two 3's, then nums = [1,4,3]
There are no more pairs that sum up to 6, hence a total of 1 operation.

Constraints:

1 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= k <= 109

Problem Summary

Given an integer array nums and an integer k. In each operation, you need to choose two integers from the array whose sum is k and remove them from the array. Return the maximum number of operations you can perform on the array.

Solution Approach

After reading the problem, my first impression is that this is an enhanced version of the TWO SUM problem. We need to find all pairs whose sum is k. First consider whether two numbers both equal to k/2 can be found. If multiple such numbers can be found, remove them first. Then use the TWO SUM approach to find pairs whose sum is k. Using the map method from TWO SUM, the time complexity is O(n).

Code

package leetcode

// Solution 1 Optimized version
func maxOperations(nums []int, k int) int {
	counter, res := make(map[int]int), 0
	for _, n := range nums {
		counter[n]++
	}
	if (k & 1) == 0 {
		res += counter[k>>1] >> 1
		// Combinations that can form k from 2 identical numbers have all been excluded; the remaining single one cannot form k either
		// So set its frequency to 0 here. If it is not set to 0 here, the logic below would still need to consider the case of reusing numbers
		counter[k>>1] = 0
	}
	for num, freq := range counter {
		if num <= k/2 {
			remain := k - num
			if counter[remain] < freq {
				res += counter[remain]
			} else {
				res += freq
			}
		}
	}
	return res
}

// Solution 2
func maxOperations_(nums []int, k int) int {
	counter, res := make(map[int]int), 0
	for _, num := range nums {
		counter[num]++
		remain := k - num
		if num == remain {
			if counter[num] >= 2 {
				res++
				counter[num] -= 2
			}
		} else {
			if counter[remain] > 0 {
				res++
				counter[remain]--
				counter[num]--
			}
		}
	}
	return res
}