Toasobi
K 和数对的最大数目(两数之和进阶)
本文最后更新于2023年09月18日,已超过476天没有更新。如果文章内容或图片资源失效,请留言反馈,我会及时处理,谢谢!
**
- 题目:
**
给你一个整数数组 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 次操作。
解法一:哈希表
这个解法是我根据之前做过的两数之和的题解拓展之后写出的,但是放在这道题上,由于其过多的操作导致其时间和空间效率都很低,因此不推荐
class Solution {
public int maxOperations(int[] nums, int k) {
int length = nums.length;
int count = 0;
HashMap<Integer, Integer> map = new HashMap<>();
if (length == 0 || length == 1)
return 0;
for (int i = 0; i < length; i++) {
if (map.containsKey(nums[i])) {
map.put(nums[i], map.get(nums[i]) + 1);
} else {
map.put(nums[i], 1);
}
if (map.containsKey(k - nums[i])) {
int value1 = map.get(k - nums[i]);
int value2 = map.get(nums[i]);
if (value1 > 0 && value2 > 0 ){
if(k - nums[i] != nums[i]){ //可能会有数字是自身相加等于k,需要另外判断
map.put(k - nums[i], map.get(k - nums[i]) - 1);
map.put(nums[i], map.get(nums[i]) - 1);
++count;
}else if(k - nums[i] == nums[i] && map.get(nums[i]) >= 2){
map.put(nums[i], map.get(nums[i]) - 2);
++count;
}
}
}
}
return count;
}
}
解法二:双指针解法
以nums=[3,2,6,-4,4,18,9,1,14,10,8],k=10为例,先使用Arrays类的sort方法对数组进行升序排序,则nums=[-4,1,2,3,4,6,8,9,10,14,18],让i指向第一个元素,即最小的那个数,让j指向最后一个元素,即最大的那个数。然后依次判断nums[i] + nums[j]的情况,直到i和j相遇,有以下3种情况:
- 如果nums[i] + nums[j] == k,则可以对数组执行的最大操作数加1,i指向后一个元素,j指向前一个元素;
- 如果nums[i] + nums[j] > k,那么让j指向前一个元素,i不变。以例子说明,-4+18=14>10,最小的数加上此时j指向的数还比k大,那么此时j指向的那个数就不可能出现在方案里了,因为其他数加上它肯定也会比k大,所以可以不用管那个数了,j--;
- 如果nums[i] + nums[j] < k,同理,可以不用管此时i指向的那个数了,i++
class Solution {
public int maxOperations(int[] nums, int k) {
// max 表示可以对数组执行的最大操作数
int max = 0;
int len = nums.length;
// 升序排序
Arrays.sort(nums);
int i = 0,j = len - 1;
while(i < j){
// 依次处理3种情况
if(nums[i] + nums[j] == k){
max++;
i++;
j--;
}else if(nums[i] + nums[j] > k){
j--;
}else{
i++;
}
}
return max;
}
}