1679. Max Number of K-Sum Pairs

[fockspaces]

1. 用 dict 來紀錄出現次數
2. 當前元素如果跟過去出現的元素配對，做消除

class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        num_dict, num_ops = {}, 0
        for num in nums:
            if num_dict.get(k - num, 0) > 0:
                num_ops += 1
                num_dict[k - num] -= 1
            else:
                num_dict[num] = num_dict.get(num, 0) + 1
        return num_ops

[fockspaces]

解法二：sorted array + two pointers

1. 先排序 list
2. 雙指針指向頭尾，看加總與 K 比大小，決定限縮方向

class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        nums.sort()
        l, r, num_ops = 0, len(nums) - 1, 0
        while l < r:
            summation = nums[l] + nums[r]
            if summation == k:
                num_ops += 1
                l, r = l + 1, r - 1
            elif summation < k:
                l += 1
            else:
                r -= 1
        return num_ops