Given an array of integers and a value. Find all the pairs that sums up to the value in O(n) time with only one pass over the array. Can you do it efficiently without any space constraint?

For example, Given A=[3, 0, -2, 1, 3, 6, 8] and sum = 6 then output pairs are: {(3, 3), (0, 6), (-2, 8)}.
O(n) time with O(n) space solution
Use a hashmap to store the value at each position of A[]. While populating the hashmap for each position i, check whether the (sum-A[i]) is contained in the hashmap. If it was contained then we found a pair. Otherwise continue searching.

O(nlgn) time with O(1) space solution
Sort the array in O(nlgn) time. Now, keep two pointers, one at the beginning and the other at the end of the sorted array. If diff=A[j]-A[i] is equal to sum then (i,j) is a pair. Otherwise if sum>diff then search for a lower element on right (i.e. decrement j). Else, search for a higher element on the left (i.e. increment i).

// O(n) with O(n) space
public static void getPairs1(final int[] input, final int sum) {
    final HashSet<Integer> h = new HashSet<Integer>();

    for (int i = 0; i < input.length; i++) {
        if (h.contains(sum - input[i])) {
            System.out.println("Pair: (" + input[i] + "," + (sum - input[i]) + ")");
        }
        h.add(input[i]);
    }
}

// O(nlgn) with O(1) space
public static void getPairs2(final int[] input, final int sum) {
    Arrays.sort(input);
    int start = 0;
    int end = input.length - 1;
    final StringBuilder sb = new StringBuilder();

    while (start <= end) {
        if (input[start] + input[end] == sum) {
            sb.append("(" + input[start] + ", " + input[end] + ")");
        } else if (input[start] + input[end] > sum) {
            end--;
        } else {
            start++;
        }
    }

    System.out.println(sb.toString());
}

 
3sum : Find group of 3 elements of array that sums to given sum
For example, given array A = {-1 0 1 2 -1 -2} and sum S = 1, A solution set is: {(-1, 0, 2), (1, 2, -2)}.

We can solve 3 sum by using 2 sum by using the fact that,

a+b+c = s
=> a+b = s-c

That is for each element c in given array find pairs (a,b) such that 
a+b = s-c where s = target sum.

The following pseudocode runs in O(n^2) time to find 3 sum elements.
Pseudocode

3sum(A[], s)
  sort(A);
  result = empty set of 3 elements group
  for i = 0 to n-2 do
      target = s-A[i];
      l = i+1;
      h = n-1;
      
      while l < h do
         2sum = A[l]+A[h];
         if 2sum == target then
            result.add(A[l], A[h], A[i]);
            end--;
            start++;
         else if 2sum > target then
             end--;
         else
             start++;
         end
      end while;
  end loop; 
 return result