1679-K 和数对的最大数目

给你一个整数数组 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

Problem: 1679. K 和数对的最大数目

[TOC]

思路

先对nums排序，在i+1往后的位置寻找k-nums[i+1]的方法会超时，虽然时间复杂度才O(nlogn),在第50个测试用例时，测试结果不超时，提交结果超时，挺奇怪的。所以只能用空间换时间了，这里选用哈希表，先对nums进行预处理，找到每个数字出现的次数。

解题方法

先预处理nums，得到哈希表map，然后遍历一次nums，如果找到匹配，那么同时更新哈希表。

复杂度

• 时间复杂度:

  添加时间复杂度, 示例： O(n)

• 空间复杂度:

  添加空间复杂度, 示例： O(n)

Code

[]

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maxOperations = function(nums, k) {
    const n=nums.length;
    const map=new Map()
    let count=0
    for(const num of nums)
    {
        map.set(num,(map.get(num)||0)+1)
    }
    for(let i=0;i<n;i++)
    {
        if(map.get(nums[i])<1)
            continue
        if((nums[i]===k/2)&&map.has(nums[i])&&map.get(nums[i])>=2)
        {
            count++
            map.set(nums[i],map.get(nums[i])-2)
        }
        if ((nums[i]!==k/2)&&map.has(k-nums[i])&&map.get(k-nums[i])>=1)
        {
            count++;
            map.set(k-nums[i],map.get(k-nums[i])-1)
            map.set(nums[i],map.get(nums[i])-1)
        }
    }
    return count;
}