Max Number of K-Sum Pairs

題目描述

給定整數陣列 nums 和整數 k，每次操作從陣列中取出兩個和為 k 的元素。回傳最多可以執行多少次操作。

輸入：nums = [1,2,3,4], k = 5
輸出：2（[1,4] 和 [2,3]）

輸入：nums = [3,1,3,4,3], k = 6
輸出：1（只有一對 [3,3]）

解題思路

排序

呼叫 Array.Sort 將 nums 升序排列，為雙指針做準備

雙指針

left = 0 指向最小值，right = n-1 指向最大值

判斷和

計算 sum = nums[left] + nums[right]。若 sum == k 則配對成功，count++，left++ 且 right--

調整

sum < k 表示需要更大的數，left++；sum > k 表示需要更小的數，right--

回傳

left ≥ right 時所有可能配對都已檢查，回傳 count

程式碼

C#

csharp

public class Solution {
    // 方法一：排序 + 雙指針
    public int MaxOperations(int[] nums, int k) {
        Array.Sort(nums);
        int left = 0, right = nums.Length - 1, count = 0;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == k) { count++; left++; right--; }
            else if (sum < k) left++;
            else right--;
        }
        return count;
    }
 
    // 方法二：HashMap（不需排序）
    public int MaxOperationsHash(int[] nums, int k) {
        var map = new Dictionary<int, int>();
        int count = 0;
        foreach (int num in nums) {
            int complement = k - num;
            if (map.GetValueOrDefault(complement) > 0) {
                count++;
                map[complement]--;
            } else {
                map[num] = map.GetValueOrDefault(num) + 1;
            }
        }
        return count;
    }
}

TypeScript

typescript

function maxOperations(nums: number[], k: number): number {
    nums.sort((a, b) => a - b);
    let left = 0, right = nums.length - 1, count = 0;
    while (left < right) {
        const sum = nums[left] + nums[right];
        if (sum === k) { count++; left++; right--; }
        else if (sum < k) left++;
        else right--;
    }
    return count;
}

Python

python

def maxOperations(nums: list[int], k: int) -> int:
    nums.sort()
    left, right, count = 0, len(nums) - 1, 0
    while left < right:
        s = nums[left] + nums[right]
        if s == k:
            count += 1
            left += 1
            right -= 1
        elif s < k:
            left += 1
        else:
            right -= 1
    return count

複雜度分析

| | Time | Space | |--|------|-------| | 排序+雙指針 | O(n log n) | O(1) | | HashMap | O(n) | O(n) |

排序法瓶頸在排序 O(n log n)，雙指針本身只需 O(n)。HashMap 法每個元素最多被查找和插入各一次，均為 O(1) 攤銷，總計 O(n)，但需要 O(n) 空間存放計數。

邊界情況

所有元素相同：例如 [3,3,3,3], k=6，每兩個配一對，共 2 對
沒有任何配對：例如 [1,2,3], k=10，所有 sum 都小於 k，回傳 0
k 小於陣列最小值的兩倍：排序後 nums[0] + nums[1] > k，不可能有配對

圖解

sorted: [1,2,3,4] k=5

left=0,right=3→

1+4=5 ✓ count=1

left=1,right=2→

2+3=5 ✓ count=2

left>=right→

回傳 2

圖表展示排序後的雙指針配對過程：最小的 1 和最大的 4 相加恰好等於 5，配對成功。接著 2 和 3 相加也是 5，再次配對。兩個指針相遇後結束，共找到 2 對。

進階觀點

💡面試追問

兩種方法如何選擇？ 排序+雙指針：時間 O(n log n)、空間 O(1)，適合空間敏感的場景。HashMap：時間 O(n)、空間 O(n)，適合追求最快時間。若面試官要求「不修改原陣列」，HashMap 更合適（排序會改變原陣列）。
跟 Two Sum 的關係？ Two Sum 找一對就停，本題找所有配對。Two Sum 的 HashMap 解法可直接擴展：找到配對後不停止，而是消耗一個計數繼續掃描。
如果允許一個元素用多次？ 變成 unbounded 問題，類似 Coin Change。需要 DP 或 greedy 根據具體約束決定。

理解測驗

🤔 為什麼排序後雙指針可以找到所有配對？

🤔 HashMap 方法中，為什麼找到互補數後要 map[complement]-- 而不是刪除？