Problem
Given an integer array nums and an integer k, return the maximum number of operations you can perform.In each operation, choose two numbers whose sum is equal to k and remove them from the array.
Example(s)
Consider the following example(s) to understand the expected input and output.Example 1
Input
nums = [1,2,3,4]
k = 5Output
2Example 2
Input
nums = [3,1,3,4,3]
k = 6Output
1Solution
This solution uses the Two Pointer technique. First, we sort the array so that the smallest element is at the beginning and the largest element is at the end.We maintain two pointers:
left starts at the beginning and right starts at the end. If nums[left] + nums[right] equals k, we have found a valid pair, so we increment the result and move both pointers inward. If the sum is less than k, we move
left forward to increase the sum. If the sum is greater than k, we move right backward to decrease the sum. The process continues until the two pointers meet.
class Solution {
public int maxOperations(int[] nums, int k) {
Arrays.sort(nums);
int left = 0;
int right = nums.length - 1;
int count = 0;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == k) {
count++;
left++;
right--;
} else if (sum < k) {
left++;
} else {
right--;
}
}
return count;
}
}Complexity
Sorting the array takesO(n log n) time, and the two-pointer traversal takes O(n) time. Therefore, the overall time complexity is O(n log n). The two-pointer traversal uses
O(1) extra space apart from the space used internally by the sorting implementation.