CareerCup

print(int a[], int n)
{
 std::set<int> arr;

 std::set::iterator<int> it;

 for(int i = 0 ; i <n ; i++)
 {
  it = arr.find(sum - a[i]);
  if(it != arr.end())
	   cout<<a[i]<<" "<<*it;
  else
	  arr.insert(a[i]);
 }

}

bool hasArrayTwoCandidates(int A[], int arr_size, int sum)
{
    int l, r;
 
    /* Sort the elements */
    quickSort(A, 0, arr_size-1);
 
    /* Now look for the two candidates in the sorted 
       array*/
    l = 0;
    r = arr_size-1; 
    while(l < r)
    {
         if(A[l] + A[r] == sum)
              return 1; 
         else if(A[l] + A[r] < sum)
              l++;
         else // A[i] + A[j] > sum
              r--;
    }    
    return 0;
}

The following code returns the indexes of the pairs which their sum is K.

public static int [] findParis(int [] array, int k){
		int [] indexes = new int [2];
		indexes[0]= indexes[1] =-1;
		Hashtable<Integer, Integer> hash = new Hashtable<Integer, Integer>();
		for (int i = 0; i < array.length; i++) {
			if(hash.containsKey(array[i])){
				indexes[0] = hash.get(array[i]);
				indexes[1] = i;
				break;
			}
			hash.put(k-array[i], i);
		}
		return indexes;
	}

Solution using HashSet.

Input:  Array of ints, int k
Output: Print all pairs from array, that will sum to k

Brainstorm:
- Brute force solution can check every possible pair to see if sum is 1, and print it out; HashSet may be necessary if dupication is necessary ... O(n^2)
- Another approach is:
  - insert all number to hashmap
  - then iterate through number array linearly
    - for each number, check if sum - number exists in hashset
      - if exists, print (number, hashsetKey) and remove the key from hashset
- This appoach O(n) with O(n) space

public void findPairs(int [] nums, int k) {
    HashSet<Integer, Boolean> hs = new HashSet<>();
    for(int i = 0; i < nums.length; i++) {
        hs.put(nums[i], true);
    }
    
    for(int i = 0; i < nums.length; i++) {
        if(hs.containsKey(k-nums[i])) {
            System.out.println("(" + nums[i] + "," + k - nums[i] + ")");
            hs.remove(k-nums[i]);
        }
    }
}

Can't we use bfs which uses queues?I think we can.