本文最后更新于436 天前,其中的信息可能已经过时,如有错误请发送邮件到yuan140457@gmail.com
1679. K 和数对的最大数目
题目描述
给你一个整数数组 nums 和一个整数 k 。
每一步操作中,你需要从数组中选出和为 k 的两个整数,并将它们移出数组。
返回你可以对数组执行的最大操作数。
输入:nums = [1,2,3,4], k = 5
输出:2
解释:开始时 nums = [1,2,3,4]:
- 移出 1 和 4 ,之后 nums = [2,3]
- 移出 2 和 3 ,之后 nums = []
不再有和为 5 的数对,因此最多执行 2 次操作。
输入:nums = [3,1,3,4,3], k = 6
输出:1
解释:开始时 nums = [3,1,3,4,3]:
- 移出前两个 3 ,之后nums = [1,4,3]
不再有和为 6 的数对,因此最多执行 1 次操作。
思路
方法:排序双指针法
- 将数据排序,用两个指针分别指向数组的头尾;
- 将两个指针指向的数求和;
- 若和大于目标,则说明太大了,需要右指针左移(可以使和变小);
- 若和小于目标,则说明太小了,需要左指针右移(可以使和变大);
- 若和等于目标,则两个指针都往中间移动,结果+1。
- 循环2步骤直至左指针不在右指针的左边。
Code
class Solution {
public:
int maxOperations(vector<int>& nums, int k) {
sort(nums.begin(),nums.end());
int i = 0, j = nums.size() - 1;
int count = 0;
while(i < j){
if(nums[i] + nums[j] == k){
i++;
j--;
count++;
}
else if(nums[i] + nums[j] < k){
i++;
}
else if(nums[i] + nums[j] > k){
j--;
}
}
return count;
}
};