1679.max-number-of-k-sum-pairs.py

#
# @lc app=leetcode id=1679 lang=python3
#
# [1679] Max Number of K-Sum Pairs
#
# https://leetcode.com/problems/max-number-of-k-sum-pairs/description/
#
# algorithms
# Medium (55.77%)
# Likes:    3313
# Dislikes: 102
# Total Accepted:    429.9K
# Total Submissions: 770.8K
# Testcase Example:  '[1,2,3,4]\n5'
#
# 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^5
# 1 <= nums[i] <= 10^9
# 1 <= k <= 10^9
#
#
#

# @lc code=start

from typing import List


class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        freq = {}
        result = 0
        for i in nums:
            if freq.get(k - i, 0) > 0:
                result += 1
                freq[k - i] -= 1
            else:
                freq[i] = freq.get(i, 0) + 1
        return result
# @lc code=end