CareerCup

Most of the answers here are either N*M or NlogN in runtime. Even the C++ set solution, because creating it and searching for all elements is NlogN. There's a solution of N+M which is optimal. Build a dictionary from array B (run time M). Search in it the diffrence from n for every element from array A.
Implementation in JavaScript:

function findPair(a, b, n){
    let res = [];
    let dictionaryB = [];
    for(let number of b){
        dictionaryB[number] = true;
    }
    for(let number of a){

        if(dictionaryB[n - number]){
            res.push([number, n - number])
        }

    }
    return res;
}

console.log(findPair([1,2,3,4,5],[4,2,3,0], 5));

// ZoomBA
A = [1,2,4,-6,5,7,9]
B = [3, 6, 3, 4, 0 ]
res = join ( A, B ) :: { 5 == sum($.o) }
println(res)

int a[] = {4,6,5,0,1,3,2};
		int b[] = {0, -2, -1, 4, 6,3,3,2,1};
		int n = 5;
		for(int i = 0; i< a.length; i++)
			for(int j= 0; j<b.length; j++)
			{
				if(a[i]+b[j] == n)
				{
					System.out.println("( "+ a[i] + " , " + b[j] + " )");
				}
			}

public class PairSum {

	public static void printPair(int a[], int b[], int sum){
		
		for(int i = 0; i < a.length; i++)
		{
			for(int j = 0; j < b.length; j++)
			{
				if(a[i] + b[j] == sum)
					System.out.println("(" + a[i] + "," + b[j] +")");
			}
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a[] = {1,2,4,-6,5,7,9};
		int b[] = {3, 6, 3, 4, 0};
		int sum = 5;
		
		printPair(a, b, sum);
	}

}

The below logic is O(n logn) and space O(n) but we can reduce space complexity by running sort on the vec2.

vector<pair<int, int>> PairSum(vector<int> vec1, vector<int> vec2, int sum) {
	vector<pair<int, int>> result;
	set<int> tree2(vec2.begin(), vec2.end());

	for (auto v1 : vec1) {
		int v2 = sum - v1;
		if (tree2.find(v2) != tree2.end()) result.push_back(pair<int, int>(v1, v2);
	}

	return result;
}

simple and easy code

#include<bits/stdc++.h>
using namespace std;
void print(vector<int>vec1,vector<int> vec2,int sum)
{
unordered_set<int> s;
for(int i=0;i<vec1.size();i++)
s.insert(vec1[i]);
for(int j=0;j<vec2.size();j++)
if(s.find(sum-vec2[j])!=s.end())
cout<<sum-vec2[j]<<" "<<vec2[j]<<endl;
}

int main()
{
int n,m;
cin>>n>>m;
vector<int> vec1(n),vec2(m);
for(int i=0;i<n;i++)
cin>>vec1[i];
for(int i=0;i<m;i++)
cin>>vec2[i];
int sum;
cin>>sum;
print(vec1,vec2,sum);

}

// C/C++ program to segregate even and odd nodes in a
// Linked List
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
int a[] = {1,2,3,4,5,6};
int ans = 5;
int i,j,k;
int sum=0;
int count= 0;
i = sizeof(a)/sizeof(a[0]);


for(j=0;j<i;j++)
{ for(k=0;k<i;k++)
{
if(a[j] + a[k] == ans)
{printf("%d %d", a[j], a[k]);
printf("\n");}
}}

}

1. Sort numbers in Array1 and Array2.
2. Start i pointer from beginning of array1 and j from end of array2.
3. sum = arr1[i] + arr2[j]
4. If sum < desiredSum then i++;
5. else if sum > desiredSum then j--;
6. else print (i,j) and i++.

It can be done in O(N+M) time and O(min(N,M)) space by creating a hash map recording the frequencies of occurrence of each element of the smaller list first. Then we iterate through the other list and for each element x, add H(n-x) to our total count, where H(n-x) obtains the frequency of n-x in the smaller list. This yields the total pair count.

var a = [1, 2, 4, -6, 5, 7, 9]; 
var b = [3, 6, 3, 4, 0];


// start the loop on smaller one
var n = 5;
var map = {};

for(var i=0; i < b.length;i++) {
  map[(n - a[i])] = a[i];
}


for(var i=0; i < b.length;i++) {
  if(map[b[i]]) {
    console.log(b[i] +":"+map[b[i]])
  }
}

//complexity o(m+n)

class Pair {
int x ;
int y;

Pair(int x, int y) {
this.x = x;
this.y = y;
}


public String toString() {
return x + "," + y;
}
}

private static List<Pair> uniquePairs(int[] A, int[] B, int n) {
List<Pair> res = new ArrayList<>();
if( A == null || A.length == 0 || B == null || B.length == 0) {
return res;
}

Arrays.sort(A);
Arrays.sort(B);
HashMap<Integer, Integer> map = new HashMap<>();
for(int num : A) {
if(!map.containsKey(num)){
map.put(num, 1);
} else {
map.put(num, map.get(num) + 1);
}
}

for(int num : B) {
if( map.containsKey(n - num)) {
Pair tmp = new Pair(n - num, num);
res.add(tmp);
map.remove(n - num);
}
}

return res;
}

int a[] = {4,6,5,0,1,3,2};
int b[] = {0, -2, -1, 4, 6,3,3,2,1};
int n = 5;
for(int i = 0; i< a.length; i++)
for(int j= 0; j<b.length; j++)
{
if(a[i]+b[j] == n)
{
System.out.println("( "+ a[i] + " , " + b[j] + " )");
}
}