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;
    }
}

All Problems

All Solutions