題目敘述
題目會給定我們一個整數陣列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
