[LeetCode 解題紀錄] 1679. Max Number of K-Sum Pairs

Sean Chou

Published in

Recording everything

7 min readJun 1, 2024

1679. Max Number of K-Sum Pairs

https://leetcode.com/problems/max-number-of-k-sum-pairs/

Problem:

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 <= 105
1 <= nums[i] <= 109
1 <= k <= 109

題意

這題目要求我們找到一個整數數組 nums 中，可以進行多少次兩兩配對，使得配對後的兩數和等於給定的數字 k。每配對一次，需要將這兩個數字從數組中移除。

問題解析：

找出「有幾對相加是 k 的 pair」
pair = x + (k - x)
每配對一次，需要將這兩個數字從數組中移除 → 代表不能重複使用

解法

暴力解

一開始如果想不太到解法，可以先從最直覺的暴力法開始練習思考。

我們的目標是要找出這個陣列之中，有幾組相加是 k pair 的組合，且不能重複被使用，最直覺的做法就是兩個迴圈，從頭找到尾，並且有另一個 array來記錄這個值有沒有被使用過。

const maxOperations = function(nums, k) {
    const len = nums.length;
    // used: 用來紀錄與檢查每一個值有沒有被使用過
    const used = new Array(len);
    let pairs = 0;
    if (len < 2) return pairs;

    for (let i = 0; i < len; i++) {
        // 如果被用過，就到下一個回合
        if (used[i]) continue;
        const x = nums[i];
        for (let j = i + 1; j < len; j++) {
            if (used[j]) continue;
            if (x + nums[j] === k) {
                used[j] = 1;
                pairs++;
                break;
            }
        }
        used[i] = 1;
    }
    return pairs;
};

想當然這個解法會直接 Time Limit Exceeded

時間複雜度：O(n²)
空間複雜度：O(n)

用空間換取時間 — 使用 Hash Table

為何減少每次的比對，我們可以使用一個 hash table 來跟蹤每個數字出現的次數，這樣可以在遍歷數組時快速找到是否存在另一個數字使其和等於 k

建立一個 hash table: countMap，用來記錄每個數字出現的次數。
初始化操作次數 operations 為 0。
遍歷數組 nums，對於每個數字 num：

計算需要配對的數字 complement，使得 num + complement = k，即 complement = k - num。
如果 countMap 中有 complement 且次數大於 0，說明找到了可以配對的數字，則操作次數加 1，並更新 hash table 中 complement 的次數。
如果沒有找到配對的數字，則將 num 加入 countMap 中。

const maxOperations = function(nums, k) {
    let countMap = new Map();
    let operations = 0;
    
    for (let num of nums) {
        let complement = k - num;
        
        if (countMap.get(complement) > 0) {
            operations++;
            countMap.set(complement, countMap.get(complement) - 1);
        } else {
            countMap.set(num, (countMap.get(num) || 0) + 1);
        }
    }
    return operations;
}

時間複雜度：O(n)
空間複雜度：O(n)

減少額外空間使用 — 使用 Two Pointers

如果想要降低空間複雜度的話，另一種解法是可以使用雙指針 (Two Pointers) ，透過先對數組進行排序，然後用兩個指針從數組的兩端開始，向中間移動，尋找和為 k 的 pair。

先將數組 nums 排序。
初始化兩個指針：一個指向數組的起始位置 (left)，另一個指向數組的末尾 (right)。
不斷移動兩個指針，直到它們相遇：

如果兩指針指向的數字之和等於 k，計數器加 1，並同時移動兩個指針。
如果和小於 k，左指針右移。
如果和大於 k，右指針左移。

const maxOperations = function(nums, k) {
    // 先將數組排序
    nums.sort((a, b) => a - b);
    let left = 0;
    let right = nums.length - 1;
    let pairs = 0;

    // 使用Two Pointers進行遍歷
    while (left < right) {
        const sum = nums[left] + nums[right];

        if (sum === k) {
            pairs++;
            left++;
            right--;
        } else if (sum < k) {
            left++;
        } else {
            right--;
        }
    }

    return pairs;
};