【数据结构和算法】 K 和数对的最大数目
其他系列文章导航
Java基础合集
数据结构与算法合集设计模式合集
多线程合集
分布式合集
ES合集
文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
2.1 方法一：双指针排序
三、代码
3.1 方法一：双指针排序
3.2 方法二：两次遍历 hash 法
3.3 方法三：一次遍历 hash 法
四、复杂度分析
4.1 方法一：双指针排序
4.2 方法二：两次遍历 hash 法
4.3 方法三：一次遍历 hash 法
前言
这是力扣的 1679 题，难度为中等，解题方案有很多种，本文讲解我认为最奇妙的一种。
一、题目描述
给你一个整数数组 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
二、题解
本题其实有很多种解法，比方说两次遍历 hash 法，一次遍历 hash 法，但这些方法都不如双指针排序法简洁干练，销量也没双指针排序法高。
两次遍历 hash 法：时间复杂度O(n),空间复杂度O(n)。
一次遍历 hash 法：时间复杂度O(n),空间复杂度O(n)。
双指针排序法：时间复杂度O(nlogn + n),空间复杂度O(1)。
但按理说排序的时间复杂度是大于 hash 的，但是他的代码效率反而更高，说明 hash 算法的效率太低，或者冲突严重。
在下面我也会贴两次遍历 hash 法和一次遍历 hash 法的代码，解题思路就不讲解了。
2.1 方法一：双指针排序
思路与算法：
1. 首先先将数组排序，在设定左右指针 i 和 j ，分别指向数组的头和尾。
2. 将两个指针指向的数进行求和：
- 若和大于目标，则说明太大了，需要右指针左移（可以使和变小）。
- 若和小于目标，则说明太小了，需要左指针右移（可以使和变大）。
- 若和等于目标，则两个指针都往中间移动，结果 + 1 。
3. 循环2步骤直至左指针不在右指针的左边。
三、代码
3.1 方法一：双指针排序
Java版本：
class Solution {public int maxOperations(int[] nums, int k) {int count = 0, i = 0, j = nums.length - 1;Arrays.sort(nums);while (i < j) {if (nums[i] + nums[j] == k) {count++;i++;j--;} else if (nums[i] + nums[j] > k) {j--;} else {i++;}}return count;}
}C++版本：
#include <algorithm>
#include <vector>class Solution {
public:int maxOperations(std::vector<int>& nums, int k) {int count = 0;std::sort(nums.begin(), nums.end());int i = 0, j = nums.size() - 1;while (i < j) {if (nums[i] + nums[j] == k) {count++;i++;j--;} else if (nums[i] + nums[j] > k) {j--;} else {i++;}}return count;}
};
Python版本：
class Solution:def maxOperations(self, nums: List[int], k: int) -> int:count = 0nums.sort()i, j = 0, len(nums) - 1while i < j:if nums[i] + nums[j] == k:count += 1i += 1j -= 1elif nums[i] + nums[j] > k:j -= 1else:i += 1return count
3.2 方法二：两次遍历 hash 法
Java版本：
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获取xint i = map.get(num);//如果次数小于等于0，说明数据被使用过了【就算后面遍历到他，也可以跳过了】if (i <= 0) {continue;}//统计数量减一，先减去，防止两个相同的数据相加达到K，而只有一个数据//【有个大兄弟有疑问，为什么直接删了。补充一下：因为是两遍循环，第一次就统计过所有的数据了，如果后面的if无法进入，那么之后也不可能了，删了就删了，无所谓了。】map.put(num, i - 1);// 是否有 另一个数据。且统计的数量大于0if (map.containsKey(x) && map.get(x) > 0) {result++;//结果+1map.put(x, map.get(x) - 1);// 数量减一}}return result;}
}3.3 方法三：一次遍历 hash 法
Java版本：
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获取xInteger i = map.get(x);// 是否有 另一个数据。且统计的数量大于0if (i != null && map.get(x) > 0) {result++;//结果+1map.put(x, map.get(x) - 1);// 数量减一continue;}//这个数没有被使用，统计数量+1Integer count = map.getOrDefault(num, 0);map.put(num, count + 1);}return result;}
}四、复杂度分析
4.1 方法一：双指针排序
- 时间复杂度O(nlogn + n)。
- 空间复杂度O(1)。
4.2 方法二：两次遍历 hash 法
- 时间复杂度O(n)。
- 空间复杂度O(n)。
4.3 方法三：一次遍历 hash 法
- 时间复杂度O(n)。
- 空间复杂度O(n)。