# Leetcode - Max Number of K-Sum Pairs

Ji Kim·2021년 1월 21일
0

## Algorithm

목록 보기
34/34

Leetcode : Max Number of K-Sum Pairs

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
# Remove numbers 1 and 4, then nums = [2,3]
# Remove numbers 2 and 3, then nums = []

Example 2

Input

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


Output

1

Approach

Create a hash-table to contain each number and the target number (k - num) for every iteration. When the target number already exists in the hash-table, decrement the value by one and increment the answer.

Solution (Python)

class Solution(object):
def maxOperations(self, nums, k):
hash = defaultdict(int)
cnt = 0

for num in nums:
target = k - num

if hash[target] > 0:
hash[target] -= 1
cnt += 1
else:
hash[num] += 1

return cnt 

Result

Runtime : 592ms
Memory Usage : 23.5MB
Runtime Beats 74.91% of Python Submission

if this then that