LeetCode 1679: Max Number of K-Sum Pairs

第一個想法是用兩個指標模擬「被加數 + 加數」，找到就把兩個元素 pop 掉再重頭找。寫完才發現 pop 是 O(n)、又每次重頭，時間複雜度會變成 O(n²) 以上。後來排序後用雙指標，邏輯就清楚多了。

題目

題目連結：LeetCode 1679. Max Number of K-Sum Pairs

給定一個整數陣列 nums 和整數 k，每次操作可以從陣列中選兩個數字，若它們的和等於 k，就移除這兩個數字並計數一次。回傳最多可以執行幾次這樣的操作。

Example:

• Input: nums = [1, 2, 3, 4], k = 5

• Output: 2（配對為 (1,4) 和 (2,3)）

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

• Output: 1（只能配出一組 (3,3)）

核心思路

排序後，陣列從小到大排列，我們可以用雙指標從兩端往中間夾：

$\text{sum} = \text{nums}[left] + \text{nums}[right]$

• sum == k：成功配對，count++，兩端各內縮一步
• sum < k：總和太小，需要更大的數，left++
• sum > k：總和太大，需要更小的數，right--

排序後指標移動方向是確定的，不需要回頭，因此只需一次遍歷。

走一遍範例

用 nums = [1, 2, 3, 4]、k = 5，排序後仍為 [1, 2, 3, 4]：

Table: 雙指標移動過程

最終答案為 2。

為什麼初解 O(n²) 不好

初解的問題出在 nums.pop(index) 這個操作：

1. pop(i) 是 O(n)，因為要把後面的元素全部往前搬
2. 每次配對成功後從頭重新找，等於巢狀搜尋了
3. 最差是 $O(n^2)$ 甚至更高（加上搬移成本）

排序後用雙指標，不需要實際刪除元素，只移動指標，乾淨很多。

程式碼

初次解法（O(n²)）

from typing import List

def maxOperations(nums: List[int], k: int) -> int:
    count = 0
    augend = 0
    addend = 1

    while augend < len(nums):
        if addend >= len(nums):
            augend += 1
            addend = augend + 1  # 重置 addend
            continue

        if nums[augend] + nums[addend] == k:
            count += 1
            nums.pop(augend)
            nums.pop(addend - 1)
            augend = 0
            addend = 1
        else:
            addend += 1

    return count

最佳解法（O(n log n)）

from typing import List

def maxOperations(nums: List[int], k: int) -> int:
    nums.sort()

    left = 0
    right = len(nums) - 1
    count = 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

print(maxOperations([1, 2, 3, 4], 5))       # 2
print(maxOperations([3, 1, 3, 4, 3], 6))    # 1

注意：程式碼中避免用 sum 當變數名，因為它會 Python 有內建sum函式。

複雜度

• 時間複雜度：$O(n \log n)$。排序主導，雙指標遍歷只需 $O(n)$。
• 空間複雜度：$O(1)$。只用了常數個額外變數（排序是原地進行）。

小結

這題的核心是「排序後雙指標夾擊」，指標只需單向移動。初解 pop 的教訓也值得記住：刪除中間元素很貴，能不刪就不刪，改用指標跳過是更好的思路。

同樣的雙指標技巧在 11. Container With Most Water 和 15. 3Sum 也會用到，可以一起練習。