1679. Max Number of K-Sum Pairs

[songyy5517]

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.

Intuition The problem is to find all pairs in the array that sum up to k. Consider finding pairs, a straightforward idea is to first sort the array in ascending order. Then we use to two collision pointers starting from the left and right side respectively. While moving two pointer towards each other, we compare the sum of the two pointers with k, record the number of valid pairs, and update pointers correspondingly.

[songyy5517]

Approach: Sort & Two Pointers

1. Exception handling;
2. Sort the array in ascending order;
3. Define variables:
   • Two collision pointers starting from both sides of the array;
   • A global variable to record the number of valid pairs.
4. Scan the array, and compare the sum of two pointers with k: （1）If they are equal, then move both pointers to the next position, and update the global variable; （2）If sum > k, move the right pointer; otherwise, move the left pointer.
5. Return the global variable.

Complexity Analysis

• Time complexity: $O(N\log N)$ , performing quick sort costs $O(N\log N)$ time, and scanning the array takes $O(N)$ time, so $O(N\log N) + O(N) = O(N\log N)$ ;
• Space complexity: $O(\log N)$ , additionally define constant-sized variables, but quick sort takes $O(\log N)$ space.

[songyy5517]

class Solution {
    public int maxOperations(int[] nums, int k) {
        // Intuition: Two pointers (Collision).
        // 1. Exception handling
        if (nums == null || nums.length == 0)
            return 0;

        // 2. Define two pointers and a global variable
        int left = 0, right = nums.length - 1;
        int num = 0;

        // 3. Sort the array.
        Arrays.sort(nums);

        // 4. Loop through the array
        while (left < right){
            if (nums[left] + nums[right] == k){
                num ++;
                left ++;
                right --;
            }
            else if (nums[left] + nums[right] > k)
                right --;
            else
                left ++;
        }

        return num;
    }
}

[songyy5517]

2024/5/11