LeetCode 日記 #010: 1679. Max Number of K-Sum Pairs｜HashTable｜Counter｜Greedy

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

• Example 2:
  Input: nums = [3,1,3,4,3], k = 6
  Output: 1

思路

題目說的是要找出陣列中，兩值的和會等於 k 的元素，最後計算出有幾對並返回。

1. 重點在於查找方式，因為可以用迭代方式判斷是否包含 k - num 的數字，所以關鍵在於快速查找 (k - num)。

   而提到快速查找通常最先想到會是 HashTable -> O(1)

2. 第二個重點是不能重複計算元素，被計算過的就要被移除，但首先陣列不能移除元素，而列表移除會改變長度，所以應該要用 counter 來計算 (?)

   用 HashTable 作為 counter，先計算每個值出現的次數，每當有組合達成條件就扣除出現的次數，直到沒有辦法達成條件為止。

3. 計算組合次數，每當有一個組合達成條件時，除了扣除 counter 裡的次數，也要累計組合的次數。

4. 需要注意的 Edge Case 是當兩個元素的值相同時，需要確保在 counter 裡的次數是至少等於 2。

Code

時間跟空間複雜度都是 O(n)，時間的增長量主要在迭代次數，空間是每次迭代要存入的 complement 變數。

class Solution {
    public int maxOperations(int[] nums, int k) {
        Map<Integer, Integer> map = getCountMap(nums);
        int count = 0;
        for (int num : nums) {
            if (map.getOrDefault(num, 0) > 0) {
                int complement = k - num;
                if (isMatch(map, num, complement)) {
                    map.put(num, map.get(num) - 1);
                    map.put(complement, map.get(complement) - 1);
                    count++;
                }
            }
        }
        return count;
    }

    private boolean isMatch(Map<Integer, Integer> map, int num, int complement) {
        return num != complement && map.getOrDefault(complement, 0) > 0 ||
                    num == complement && map.getOrDefault(complement, 0) > 1;
    }

    private Map<Integer, Integer> getCountMap(int[] nums) {
        return Arrays.stream(nums)
                    .boxed()
                    .collect(Collectors.toMap(
                        num -> num,
                        num -> 1,
                        (existing, replacement) -> existing + 1
                    ));
    }
}

Takeaway

• 用 Map 作為 Counter 計算值出現的次數。重複的 key 會合併，用 getOrDefault 來計算的方法很巧妙。

• 用 HashTable 查找的複雜度是 O(1)。

• Stream 的練習。

• 配對問題模式：這類尋找配對元素的問題很常見，掌握這種模式有助於快速識別和解決類似問題。

• 模擬操作與實際操作：有時候不需要實際修改數據結構（如移除元素），而是可通過模擬操作（如減少計數）來達到同樣的效果，這通常更高效。