1679. K 和數對的最大數目 - 力扣（LeetCode）

題目

給你一個整數數組?nums?和一個整數?k?。

每一步操作中，你需要從數組中選出和為?k?的兩個整數，并將它們移出數組。

返回你可以對數組執行的最大操作數。

示例 1：

輸入：nums = [1,2,3,4], k = 5
輸出：2
解釋：開始時 nums = [1,2,3,4]：
- 移出 1 和 4 ，之后 nums = [2,3]
- 移出 2 和 3 ，之后 nums = []
不再有和為 5 的數對，因此最多執行 2 次操作。

示例 2：

輸入：nums = [3,1,3,4,3], k = 6
輸出：1
解釋：開始時 nums = [3,1,3,4,3]：
- 移出前兩個 3 ，之后nums = [1,4,3]
不再有和為 6 的數對，因此最多執行 1 次操作。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 1 <= k <= 109

思路

1. 先將數組排序，然后再左右匹配。

代碼實現

class Solution {
public:int maxOperations(vector<int>& nums, int k) {int l = 0, r = nums.size()-1, cnt = 0, sum;if (r < 1)return 0;sort(nums.begin(), nums.end());while (l < r) {sum = nums[l]+nums[r];if (sum == k) {l++;r--;cnt++;} else if(sum < k) l++;else r--;}return cnt;}
};

復雜度分析

• 時間復雜度：O(n)。
• 空間復雜度：O(1)。

其他題解

• 還有一種方法也挺有意思的，就是利用哈希表，先將nums中的數字情況存入哈希表，然后再遍歷一遍數組，每次遇到x時就找哈希表key為k-x是否還可以匹配，可以就將map[k-x]的value減一，然后完成匹配，最后結果除以2即可（因為對應的匹配肯定是成對存在的，所以會重復一次）。
• 這個時空間復雜度都是O(n)的，所以就不復現了。