Finding Pairs With A Certain Sum - Leetcode Solution

Problem Statement:

Given an array of integers nums and an integer target, return the number of pairs i, j (i < j) such that nums[i] + nums[j] == target.

Example:

Input: nums = [1,2,3,4,5], target = 5 Output: 2 Explanation: Pairs of numbers that add up to 5 are (1, 4) and (2, 3).

Solution:

Approach:

One of the approaches to solve this problem is using two pointers technique. We can solve this problem by maintaining two pointers, one pointing to the start of the array and another pointing to the end of the array. As the array is sorted, the two pointer technique will help us reach the solution.

Algorithm:

1. Sort the array in increasing order.
2. Initialize two pointers, one pointing to the start of the array and another pointing to the end of the array.
3. Traverse through the array, keeping in mind i is less than j (i < j).
4. We can calculate the sum of the elements at the i-th and j-th index of the array.
5. If the sum of the two elements is equal to the target, then increment the counter.
6. If the sum of the two elements is less than the target, then increment the index of the i-th pointer as the array is sorted in increasing order.
7. If the sum of the two elements is greater than the target, then decrease the index of the j-th pointer as the array is sorted in increasing order.
8. Repeat the above steps until the two pointers cross or collide.

Code:

int nums = {1,2,3,4,5}; int target = 5;

sort(nums.begin(), nums.end()); // Sort the array in increasing order.

int i = 0, j = nums.size() - 1; // Initialize two pointers.

int count = 0;

while(i < j) {

if(nums[i] + nums[j] == target) { // If the sum of the two elements is equal to the target.

    count++; // Increment the counter.
    i++; // Move the i-th index pointer.
    j--; // Move the j-th index pointer.

} else if(nums[i] + nums[j] < target) { // If the sum of the two elements is less than the target.

    i++; // Move the i-th index pointer.

} else { // If the sum of the two elements is greater than the target.

    j--; // Move the j-th index pointer.

}

}

return count; // Return the answer.

Time Complexity:

The time complexity of this algorithm is O(NLogN) because of the time taken for the sorting of the array. The two pointer traversal of the array takes O(N) time after the initial sorting. So, the overall time complexity of the algorithm is O(NLogN) + O(N) = O(NLogN).

1