Max Number of K Sum Pairs

1679. K和数对的最大数目

分析

使用哈希表记录出现次数：
- 用一个哈希表 hash 来记录数组中每个整数出现的次数
查找是否能形成和为 k 的配对：
- 遍历数组中的每个元素 num，计算目标值 target = k - num
- 如果哈希表中存在目标值 target 且次数大于 0，则找到一对符合条件的整数，计数器 res 增加 1，并减少 target 的计数
- 如果目标值 target 不存在，将当前元素 num 的计数加到哈希表中
返回最大操作数：
- 遍历完成后，结果存储在 res 中，表示可以执行的最大操作数

时间复杂度

遍历数组，时间复杂度为 O(n)
每次哈希表的插入与查询时间复杂度为 O(1)，总体复杂度为 O(n)

空间复杂度

空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution
{
public:
    int maxOperations(vector<int>& nums, int k)
    {
        std::unordered_map<int, int> hash; // 哈希表记录元素出现次数
        int res = 0; // 记录最大操作数

        for (int num : nums) // 遍历数组
        {
            int target = k - num; // 计算需要配对的目标值
            if (hash[target] > 0) // 如果目标值存在于哈希表中
            {
                --hash[target]; // 配对目标值计数减一
                ++res; // 操作数加一
            }
            else
            {
                ++hash[num]; // 当前元素加入哈希表
            }
        }
        return res;
    }
};