class Solution {
public:
int maxOperations(vector<int>& nums, int k) {
}
};
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 <= 1051 <= nums[i] <= 1091 <= k <= 109原站题解
java 解法, 执行用时: 34 ms, 内存消耗: 51.8 MB, 提交时间: 2022-12-17 15:50:54
/**
* 一遍循环hash法
**/
class Solution {
public int maxOperations(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>(nums.length);
int result = 0;
//统计每个数据出现的次数，key为数据，value为次数
for (int num : nums) {
// 获取求和的另一个数
int x = k - num;
// 从map获取x
Integer i = map.get(x);
// 是否有 另一个数据。且统计的数量大于0
if (i != null && map.get(x) > 0) {
result++;//结果+1
map.put(x, map.get(x) - 1);// 数量减一
continue;
}
//这个数没有被使用，统计数量+1
Integer count = map.getOrDefault(num, 0);
map.put(num, count + 1);
}
return result;
}
}
java 解法, 执行用时: 47 ms, 内存消耗: 51.9 MB, 提交时间: 2022-12-17 15:50:26
/**
* 两遍循环hash法
**/
class Solution {
public int maxOperations(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>(nums.length);
//统计每个数据出现的次数，key为数据，value为次数
for (int num : nums) {
Integer i = map.getOrDefault(num, 0);
map.put(num, i + 1);
}
int result = 0;
for (int num : nums) {
// 求和达到K的数据
int x = k - num;
// 从map获取x
int i = map.get(num);
//如果次数小于等于0，说明数据被使用过了【就算后面遍历到他，也可以跳过了】
if (i <= 0) {
continue;
}
//统计数量减一，先减去，防止两个相同的数据相加达到K，而只有一个数据
//【有个大兄弟有疑问，为什么直接删了。补充一下：因为是两遍循环，第一次就统计过所有的数据了，如果后面的if无法进入，那么之后也不可能了，删了就删了，无所谓了。】
map.put(num, i - 1);
// 是否有 另一个数据。且统计的数量大于0
if (map.containsKey(x) && map.get(x) > 0) {
result++;//结果+1
map.put(x, map.get(x) - 1);// 数量减一
}
}
return result;
}
}
java 解法, 执行用时: 18 ms, 内存消耗: 51.7 MB, 提交时间: 2022-12-17 15:50:00
/**
* 排序+双指针
**/
class Solution {
public int maxOperations(int[] nums, int k) {
int result = 0;
//排序
Arrays.sort(nums);
//头尾指针
int i = 0, j = nums.length - 1;
while (i < j) {
int sum = nums[i] + nums[j];
if (k == sum) {//刚好相等。两个指针都往中间移动
result++;
i++;
j--;
} else if (k > sum) {//两数之和太小，左指针右移，让和变大
i++;
} else {//两数之和太大，右指针左移，让和变小
j--;
}
}
return result;
}
}
python3 解法, 执行用时: 132 ms, 内存消耗: 25.5 MB, 提交时间: 2022-12-17 15:48:58
class Solution:
def maxOperations(self, nums: List[int], k: int) -> int:
mp = defaultdict(int)
ans = 0
for num in nums:
if mp[k-num] > 0:
ans += 1
mp[k-num] -= 1
else:
mp[num] += 1
return ans