最多可以製造幾個K-sum pairs_Leetcode 精選75題

Edge2Edge Media null on Unsplash

題目敘述

題目會給定我們一個整數陣列nums，我們每回合可以挑選總和為K的兩個數字，形成一個K-Sum pair。

請問我們最多可以製造幾個K-Sum pair?

題目的原文敘述

測試範例

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 <= 10^5

輸入陣列nums的長度介於1和10^5之間。

• 1 <= nums[i] <= 10^9

陣列內每個數字都介於1~10^9之間。

• 1 <= k <= 10^9

k值介於1~10^9之間。

演算法

這題題目問的是有幾個K-sum pair，其實如果把K當成2的話，就變成two-sum pair了，這題基本上可以視為 Leetcode #1 Two sum的進階延伸推廣。

可以分成兩種情況討論:

第一種情況: nums[i] + nums[j] = k, 而且 nums[i] 不等於 nums[j]

也就是說，這個pair是由一大一小的數字所組成，總和為k。

例如測試範例中的

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