Leetcode 1679. Max Number of K-Sum Pairs

문제

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.

정수배열 nums와 정수 k가 주어집니다.
한번의 연산을 통해 nums에서 합쳤을때 k가 되는 두 원소를 제거할수 있습니다.
nums에서 위 연산을 수행할수 있는 최대 횟수를 리턴하시오.

예시

Input: nums = [1,2,3,4], k = 5
Output: 2
Explanation: [1, 2, 3, 4] 에서 시작한다.
1 + 4 = 5 이기에 연산에 의해 삭제되고 [2, 3]이 남는다.
2 + 3 = 5 이기에 연산에 의해 삭제되고 [] 가 남는다.
더 이상 배열이 비어 연산이 불가능하기에 지금까지 수행한 연산의 횟수인 2가 리턴된다.

제한

• $1 <= nums.length <= 10^5$
• $1 <= nums[i] <= 10^9$
• $1 <= k <= 10^9$

풀이

더블 포인터를 사용하는 방법

1. 주어진 nums 를 오름차순으로 정렬한다.

nums.sort()

2. 왼쪽과 오른쪽에 포인터를 두고 아래와 같이 이동한다.
   • 왼쪽 포인터의 값 + 오른쪽 포인터의 값이
     • 타겟보다 작으면 -> 왼쪽 포인터를 오른쪽으로 한칸 이동한다.
     • 타겟보다 크면 -> 오른쪽 포인터를 왼쪽으로 한칸 이동한다.
     • 타겟과 같으면 -> 두 포인터를 모두 이동하고 연산 횟수를 1회 카운트 한다.
     • 만약 왼쪽 포인터보다 오른쪽 포인터가 작거나 같으면 종료한다.

• 더블 포인터를 사용해 연산하는 과정은 O(n)의 시간복잡도를 가지고, sort() 는 O(nLogn)의 시간복잡도를 가져 총 O(nLogn) 의 시간 복잡도를 가진다.

class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:

        ops, left, right = 0, 0, len(nums) - 1
        nums.sort()

        while left < right:
            if nums[left] + nums[right] > k:
                right -= 1
            elif nums[left] + nums[right] < k:
                left += 1
            else:
                ops += 1
                left += 1
                right -= 1

        return ops

Counter를 사용하는 방법

• Counter는 배열을 등장하는 횟수에 따라 Dict 형식으로 변환한다.
• 이를 이용해 미리 Dict를 만들어 Two sum을 해결하듯 한다.
• 단, 여기선 연산 횟수의 증가량은 더해지는 각각 원소의 등장횟수중 적은것 나누기 2가 된다.

class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:

        cnt = Counter(nums)
        ans = 0

        for i, _ in cnt.items():
            if k - i in cnt:
                ans += min(cnt[i], cnt[k-i])

        return ans // 2