Find all pairs with a given sum - PrismoSkills

Find all pairs with a given sum - PrismoSkills
Problem: Given an unsorted array, find all pairs whose sum is a given number K

1. Solution 1: Use a hash-map to store all numbers.
   When storing a number in the map, lookup N-k.
   If N-k exists in the map, sum is found, else move to next number.
   
   
   
2. Solution 2: Sort the array and search with two indexes set to start and end of the array.

Find all triplets with a given sum
A corollary of the above question is to find all triplets with a given sum.

Since the best case for finding pairs was O(n log n) for sorting and then O(n) for finding pairs, it
follows that the order for triplets would be greater than or equal to that.

Taking liberty due to this, let us first sort the array.

Now for each number in the sorted array, we can find a pair whose sum is S-arr[k]

Since finding pairs for a given sum is O(n) in sorted array, the whole operation becomes O(n log n ) + O(n2)

Which is equal to O(n2)

Now find all quadruples with a given sum

Find sum of all pairs using two loops - O(n2) to get k (i.e. n(n-1)/2) numbers
Sort these k numbers - O (k log k) = O(n2 log n2) = O(n2 log n)
Find pairs in these sorted 'k' numbers whose sum is the given sum and which do not have any common element from the original array.

http://www.geeksforgeeks.org/given-two-unsorted-arrays-find-pairs-whose-sum-x/

void findPairs(int arr1[], int arr2[], int n,

                               int m, int x)

{

    // Insert all elements of first array in a hash

    unordered_set<int> s;

    for (int i=0; i<n; i++)

        s.insert(arr1[i]);

 

    // Subtract sum from second array elements one

    // by one and check it's present in array first

    // or not

    for (int j=0; j<m; j++)

        if (s.find(x - arr2[j]) != s.end())

            cout << x-arr2[j] << " "

                 << arr2[j] << endl;

}

Read full article from Find all pairs with a given sum - PrismoSkills