Description

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

Solution

The description reminds me the “Two Sum” problem. We can use similar algorithm. We create a dictionary with the array value as key, the number of counts we still have (the total count we have upto the current element minus the count we’ve already used to make k) as value. When we traverse the array and everytime we found a number which add current number equals k, we can decrease the count. When we move to the next element, we need to update the count (if the current element is not in the dictionary, we set the count as 1. If it is already in the dictionary we add 1 to its count).

Below is the implementation

class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        '''
        [1,3,3,3,4]
        '''
        st = {}
        count = 0
        for num in nums:
            t = k - num
            if t in st and st[t] > 0:
                count += 1
                st[t] -= 1
            else:
                st[num] = 1 if num not in st else (st[num] + 1)
        return count

The time complexity is O(n)