703284. Two sum -Pairs with 0 Sum
Count Pairs with Given Sum (Two sum -Pairs with 0 Sum)
Summary
Given an array of integers, we need to find the number of pairs whose sum is equal to a given target sum. This problem is related to arrays and two-pointer algorithm.
Detailed Explanation
The approach for this problem involves using a two-pointer technique. First, we sort the array in ascending order. Then, we initialize two pointers, one at the start of the array (left) and one at the end of the array (right). We calculate the sum of the values at these two positions. If the sum is equal to the target sum, we increment our count by 1 and move both pointers towards each other. If the sum is less than the target sum, we move the left pointer to the right to increase the sum. If the sum is greater than the target sum, we move the right pointer to the left to decrease the sum.
Here's a step-by-step breakdown of the solution:
- Sort the array in ascending order.
- Initialize two pointers, one at the start of the array (left) and one at the end of the array (right).
- Calculate the sum of the values at these two positions.
- If the sum is equal to the target sum, increment our count by 1 and move both pointers towards each other.
- If the sum is less than the target sum, move the left pointer to the right to increase the sum.
- If the sum is greater than the target sum, move the right pointer to the left to decrease the sum.
- Repeat steps 3-6 until the two pointers meet.
Time Complexity: O(n log n) due to sorting Space Complexity: O(1)
Optimized Solutions
Java
import java.util.Arrays;
public class CountPairs {
public static int countPairs(int[] arr, int targetSum) {
Arrays.sort(arr);
int left = 0;
int right = arr.length - 1;
int count = 0;
while (left < right) {
if (arr[left] + arr[right] == targetSum) {
count++;
left++;
right--;
} else if (arr[left] + arr[right] < targetSum) {
left++;
} else {
right--;
}
}
return count;
}
}