Question
Formatted question description: https://leetcode.ca/all/1679.html
1679. Max Number of K-Sum Pairs
You are given an integer array nums and an integer k.
In one operation, you can pick two numbers from the array whose sum equals k and remove them from the array.
Return the maximum number of operations you can perform on the array.
Example 1:
Input: nums = [1,2,3,4], k = 5
Output: 2
Explanation: Starting with nums = [1,2,3,4]:
- Remove numbers 1 and 4, then nums = [2,3]
- Remove numbers 2 and 3, then nums = []
There are no more pairs that sum up to 5, hence a total of 2 operations.
Example 2:
Input: nums = [3,1,3,4,3], k = 6
Output: 1
Explanation: Starting with nums = [3,1,3,4,3]:
- Remove the first two 3's, then nums = [1,4,3]
There are no more pairs that sum up to 6, hence a total of 1 operation.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= k <= 109
Algorithm
The idea of this question is similar to two sum, we need to create a hashmap to record the numbers in the input in order to find k-nums[i]. Here I provide two implementation methods, one only needs to scan the array once, and the other needs to scan the array twice. The time and space complexity are all O(n).
Scan once
The ingenious thing about scanning once is its handling of the case when nums[i] is exactly half of K. When nums[i] is exactly half of K, then res is only + 1, so that it can be merged with other situations without scanning twice.
Code
Java
public class Max_Number_of_K_Sum_Pairs {
class Solution {
public int maxOperations(int[] nums, int k) {
int res = 0;
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
if (map.getOrDefault(k - num, 0) > 0) {
map.put(k - num, map.get(k - num) - 1);
res++;
} else {
map.put(num, map.getOrDefault(num, 0) + 1);
}
}
return res;
}
}
}Java
class Solution {
public int maxOperations(int[] nums, int k) {
int operations = 0;
Arrays.sort(nums);
int low = 0, high = nums.length - 1;
while (low < high) {
int sum = nums[low] + nums[high];
if (sum == k) {
operations++;
low++;
high--;
} else if (sum < k)
low++;
else
high--;
}
return operations;
}
}