题目
给你一个整数数组 nums 和一个整数 k 。
每一步操作中，你需要从数组中选出和为 k 的两个整数，并将它们移出数组。
返回你可以对数组执行的最大操作数。
一、代码实现
func maxOperations(nums []int, k int) int {
freq := make(map[int]int)
operations := 0
// 第一次遍历统计频率
for _, num := range nums {
if num < k { // 剪枝：大于等于k的数无法参与有效配对
freq[num]++
}
}
// 第二次遍历寻找有效配对
for num, cnt := range freq {
complement := k - num
if complement < num || freq[complement] == 0 {
continue // 避免重复处理或无效配对
}
if num == complement {
operations += cnt / 2
} else {
pairs := min(cnt, freq[complement])
operations += pairs
freq[complement] -= pairs
}
freq[num] = 0 // 标记已处理
}
return operations
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
二、算法分析
核心思路
- 哈希映射统计：通过哈希表记录每个数字出现的次数
- 对称配对原则：对于每个数
num，寻找补数k-num，统计最小出现次数作为有效配对 - 剪枝优化：忽略大于等于k的元素（无法形成有效配对）
关键步骤
频率统计：遍历数组建立数字频率哈希表（O(n)时间）
配对计算：二次遍历哈希表，处理三种情况：
- 补数不存在：跳过
- 补数等于自身：取出现次数的一半
- 补数不同：取两者出现次数的较小值
状态更新：处理完成后清空已计算元素的频率
复杂度
- 时间复杂度：
O(n)，两次线性遍历 - 空间复杂度：
O(n)，哈希表存储频率
- 时间复杂度：
三、图解
四、边界条件与扩展
- 特殊场景处理
- 全零数组：
nums = [0,0,0], k=0→ 最大操作数为1（取两零配对） - 自补数：
nums = [5,5,5], k=10→ 操作数1（需要两个5配对） - 大数干扰：
nums = [100,200], k=300→ 有效配对（需关闭剪枝条件）
- 多语言实现
- Python：使用
collections.Counter简化频率统计
def maxOperations(nums, k):
from collections import Counter
freq = Counter(num for num in nums if num < k)
return sum(min(freq[num], freq[k-num]) if num != k-num else freq[num]//2
for num in list(freq.keys())) // 2
- Java：
HashMap配合遍历优化
int maxOperations(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums)
if (num < k) map.put(num, map.getOrDefault(num, 0)+1);
int res = 0;
for (int num : map.keySet()) {
int comp = k - num;
if (comp < num || !map.containsKey(comp)) continue;
res += (num == comp) ? map.get(num)/2 :
Math.min(map.get(num), map.get(comp));
}
return res;
}
- 算法对比
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 哈希映射法 | O(n) | O(n) | 通用场景（推荐） |
| 排序+双指针 | O(n logn) | O(1) | 内存敏感场景 |
| 暴力枚举 | O(n²) | O(1) | 仅小数据量 |
五、总结
- 核心创新：通过哈希表将配对问题转化为频率统计问题
- 数学证明：设总有效配对数为
m，必满足2m ≤ n，哈希法确保遍历所有可能组合 - 优化空间：通过剪枝条件
num < k减少无效存储 - 扩展应用：可推广至三数之和等组合问题，需调整哈希策略