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 <= 10^51 <= nums[i] <= 10^91 <= k <= 10^9
The description was taken from https://leetcode.com/problems/max-number-of-k-sum-pairs/.
#O(N) Time, O(N) Space
class Solution:
def maxOperations(self, nums: List[int], k: int) -> int:
seen = {}
output = 0
for num in nums:
complement = k - num
if complement in seen:
output += 1
if seen[complement] == 1:
del seen[complement]
else:
seen[complement] -= 1
else:
if num in seen:
seen[num] += 1
else:
seen[num] = 1
return outputWe are looking for pairs of numbers that sum to a target value.
This is like the classic Two-Sum problem. Similar to that problem, we can derive a solution by storing each number in a HashMap and utilizing the x+y=z formula, solving for y. This translates to complement = k - current value.
The only tweak we will have to make is when we find a pair, we will delete the complement from our HashMap and omit the current value. This will allow us to not consider the same values twice.
Let's start by creating a dictionary for values that we have seen.
seen = {}
We'll also need an output to count how many pairs we find that sum to k.
output = 0
For each number in the nums array, we will calculate its complement.
for num in nums:
complement = k - num
If that complement has been seen, then we have a pair and will increment the output.
if complement in seen:
output += 1
If the frequency of this complement value is one, then we will delete it from our dictionary to save us a little bit of space.
if seen[complement] == 1:
del seen[complement]
Otherwise, if we have multiple of this value, then we will decrement its frequency.
else:
seen[complement] -= 1
If we just paired the current value with a value we saw previously, there's no reason to place it into the dictionary because the pairs have to be unique.
If we didn't, we will increment the current value's frequency in the dictionary or initialize its place there.
else:
if num in seen:
seen[num] += 1
else:
seen[num] = 1
Once we have traversed the array, we'll return the number of pairs we were able to find.
return output